Ebook: Computational Graph Theory
- Tags: Computer Graphics, Combinatorics, Numerical Analysis
- Series: Computing Supplementum 7
- Year: 1990
- Publisher: Springer-Verlag Wien
- Edition: 1
- Language: English
- pdf
One ofthe most important aspects in research fields where mathematics is "applied is the construction of a formal model of a real system. As for structural relations, graphs have turned out to provide the most appropriate tool for setting up the mathematical model. This is certainly one of the reasons for the rapid expansion in graph theory during the last decades. Furthermore, in recent years it also became clear that the two disciplines of graph theory and computer science have very much in common, and that each one has been capable of assisting significantly in the development of the other. On one hand, graph theorists have found that many of their problems can be solved by the use of com puting techniques, and on the other hand, computer scientists have realized that many of their concepts, with which they have to deal, may be conveniently expressed in the lan guage of graph theory, and that standard results in graph theory are often very relevant to the solution of problems concerning them. As a consequence, a tremendous number of publications has appeared, dealing with graphtheoretical problems from a computational point of view or treating computational problems using graph theoretical concepts.
Content:
Front Matter....Pages i-vii
Efficient Computations in Tree-Like Graphs....Pages 1-15
Graph Problems Related to Gate Matrix Layout and PLA Folding....Pages 17-51
Planar Graph Problems....Pages 53-68
Basic Parallel Algorithms in Graph Theory....Pages 69-91
Applications of Parallel Scheduling Algorithms to Families of Perfect Graphs....Pages 93-107
Orders and Graphs....Pages 109-124
Dynamic Partial Orders and Generalized Heaps....Pages 125-139
Communication Complexity....Pages 141-153
Path Problems in Graphs....Pages 155-189
Heuristics for Graph Coloring....Pages 191-208
Probabilistic Analysis of Graph Algorithms....Pages 209-233
Generating Graphs Uniformly at Random....Pages 235-255
Embedding one Interconnection Network in Another....Pages 257-282
Back Matter....Pages 283-285
Content:
Front Matter....Pages i-vii
Efficient Computations in Tree-Like Graphs....Pages 1-15
Graph Problems Related to Gate Matrix Layout and PLA Folding....Pages 17-51
Planar Graph Problems....Pages 53-68
Basic Parallel Algorithms in Graph Theory....Pages 69-91
Applications of Parallel Scheduling Algorithms to Families of Perfect Graphs....Pages 93-107
Orders and Graphs....Pages 109-124
Dynamic Partial Orders and Generalized Heaps....Pages 125-139
Communication Complexity....Pages 141-153
Path Problems in Graphs....Pages 155-189
Heuristics for Graph Coloring....Pages 191-208
Probabilistic Analysis of Graph Algorithms....Pages 209-233
Generating Graphs Uniformly at Random....Pages 235-255
Embedding one Interconnection Network in Another....Pages 257-282
Back Matter....Pages 283-285
....