Computational Graph Theory

1. Front Matter

   Pages i-vii

   PDF

2. Efficient Computations in Tree-Like Graphs

   • Andrzej Proskurowski, Maciej M. Syslo

   Pages 1-15

3. Graph Problems Related to Gate Matrix Layout and PLA Folding

   • Rolf H. Möhring

   Pages 17-51

4. Planar Graph Problems

   • Takao Nishizeki

   Pages 53-68

5. Basic Parallel Algorithms in Graph Theory

   • Ernst W. Mayr

   Pages 69-91

6. Applications of Parallel Scheduling Algorithms to Families of Perfect Graphs

   • David Helmbold, Ernst W. Mayr

   Pages 93-107

7. Orders and Graphs

   • Ulrich Faigle, Rainer Schrader

   Pages 109-124

8. Dynamic Partial Orders and Generalized Heaps

   • Hartmut Noltemeier

   Pages 125-139

9. Communication Complexity

   • Ulrich Faigle, György Turán

   Pages 141-153

10. Path Problems in Graphs

    • Günter Rote

    Pages 155-189

11. Heuristics for Graph Coloring

    • D. de Werra

    Pages 191-208

12. Probabilistic Analysis of Graph Algorithms

    • A. M. Frieze

    Pages 209-233

13. Generating Graphs Uniformly at Random

    • G. Tinhofer

    Pages 235-255

14. Embedding one Interconnection Network in Another

    • B. Monien, H. Sudborough

    Pages 257-282

15. Back Matter

    Pages 283-285

    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.

• Layout
• algorithms
• calculus
• computational graph theory
• graph theory
• graphs
• network
• combinatorics

• Institut für Mathematik, Technische Universität München, Federal Republic of Germany

  G. Tinhofer

• Department of Computer Science, Stanford University, USA

  E. Mayr

• Institut für Informatik, Universität Würzburg, Federal Republic of Germany

  H. Noltemeier

• Institute of Computer Science, University of Wrocław, Poland

  M. M. Syslo

Policies and ethics