Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

1990 | Book

Efficient Computations in Tree-Like Graphs Read chapter Read first chapter

Computational Graph Theory

Editors: Prof. Dr. G. Tinhofer, Prof. Dr. E. Mayr, Prof. Dr. H. Noltemeier, Prof. Dr. M. M. Syslo

Publisher: Springer Vienna

Book Series : Computing Supplementum

Included in: Professional Book Archive

Login to get access
insite
SEARCH

About this book

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.

Table of Contents

Frontmatter
Efficient Computations in Tree-Like Graphs
Abstract
Efficient Computations in Tree-Like Graphs. Many discrete optimization problems are both very difficult and important in a range of applications in engineering, computer science and operations research. In recent years, a generally accepted measure of a problem’s difficulty became a worst-case, asymptotic growth complexity characterization. Because of the anticipated at least exponential complexity of any solution algorithm for members in the class of NP-hard problems, restricted domains of problems’ instances are being studied, with hopes that some such modified problems would admit efficient (polynomially bounded) solution algorithms. We survey investigations of the complexity behavior of NP-hard discrete optimization problems on graphs restricted to different generalizations of trees (cycle-free, connected graphs.) The scope of this survey includes definitions and algorithmic characterization of families of graphs with tree-like structures that may guide the development of efficient solution algorithms for difficult optimization problems and the development of such solution algorithms.
AMS Subject Classifications: 05C; 68B, C, E, F; 90B, C.
Andrzej Proskurowski, Maciej M. Syslo
Graph Problems Related to Gate Matrix Layout and PLA Folding
Abstract
Graph Problems Related to Gate Matrix Layout and PLA Folding. This paper gives a survey on graph problems occuring in linear VLSI layout architectures such as gate matrix layout, folding of programmable logic arrays, and Weinberger arrays. These include a variety of mostly independently investigated graph problems such as augmentation of a given graph to an interval graph with small clique size, node search of graphs, matching problems with side constraints, and other. We discuss implications of graph theoretic results for the VLSI layout problems and survey new research directions. New results presented include NP-hardness of gate matrix layout on chordal graphs, efficient algorithms for trees, cographs, and certain chordal graphs, Lagrangean relaxation and approximation algorithms based on on-line interval graph augmentation.
Rolf H. Möhring
Planar Graph Problems
Abstract
Planar Graph Problems. Classical and recent results are surveyed in the development of efficient algorithms for the following eleven famous problems on planar graphs: planarity testing, embedding, drawing, separators, vertex-coloring, independent vertex set, listing subgraphs, Hamiltonian cycle, network flows, and Steiner trees and forests. Also typical methods and techniques useful for computational problems on planar graphs are discussed. Furthermore open questions on planar graphs are mentioned.
AMS Subject Classification: 05.
Takao Nishizeki
Basic Parallel Algorithms in Graph Theory
Abstract
Basic Parallel Algorithms in Graph Theory. We discuss some of the more common machine models for parallel computation and their variants, as well as some relevant basic results from parallel complexity theory. We then describe a few of the very basic and fundamental “tricks” and techniques to obtain efficient parallel algorithms. Finally, we survey work on parallel algorithms for a number of graph theoretic problems.
AMS Subject Classifications: 68E10, 68Q10.
Ernst W. Mayr
Applications of Parallel Scheduling Algorithms to Families of Perfect Graphs
Abstract
Applications of Parallel Scheduling Algorithms to Families of Perfect Graphs. We combine a parallel algorithm for the two processor scheduling problem, which runs in polylog time on a polynomial number of processors, with an algorithm to find transitive orientations of graphs where they exist. Both algorithms together solve the maximum clique problem and the minimum coloring problem for comparability graphs, and the maximum matching problem for co-comparability graphs. The transitive orientation algorithm can also be used to identify permutation graphs, another important subclass of perfect graphs.
AMS Subject Classifications: 68C15, 68E10, 68Q10.
David Helmbold, Ernst W. Mayr
Orders and Graphs
Abstract
Orders and Graphs. This paper surveys the relationship between graphtheoretic and ordertheoretic questions. In the first part, we discuss recent results which answer ordertheoretic questions in a more general graphtheoretic framework. In the second part we address ordertheoretic approaches to graph-theoretic problems.
AMS Subject Classifications: 05C20, 05C25, 06A10.
Ulrich Faigle, Rainer Schrader
Dynamic Partial Orders and Generalized Heaps
Abstract
Dynamic Partial Orders and Generalized Heaps. Classical and recent results are surveyed in the development of efficient representations of dynamic partial orders by heaps and their generalizations.
AMS Subject Classifications: 68B15, 06A10.
Hartmut Noltemeier
Communication Complexity
Abstract
Communication Complexity.In this introductory survey, the general communication complexity problem is discussed from an ordertheoretic point of view. In particular, results about special classes of ordered sets are reported. Furthermore, open problems and related ordertheoretic questions are mentioned.
AMS Subject Classification: 68C25.
Ulrich Faigle, György Turán
Path Problems in Graphs
Abstract
Path Problems in Graphs. A large variety of problems in computer science can be viewed from a common viewpoint as instances of “algebraic” path problems. Among them are of course path problems in graphs such as the shortest path problem or problems of finding optimal paths with respect to more generally defined objective functions; but also graph problems whose formulations do not directly involve the concept of a path, such as finding all bridges and articulation points of a graph. Moreover, there are even problems which seemingly have nothing to do with graphs, such as the solution of systems of linear equations, partial differentiation, or the determination of the regular expression describing the language accepted by a finite automaton.
We describe the relation among these problems and their common algebraic foundation.
We survey algorithms for solving them: vertex elimination algorithms such as Gauß-Jordan elimination; and iterative algorithms such as the “classical” Jacobi and Gauß-Seidel iteration.
AMS 1980 mathematics subject classification (1985 revision): 68–01, (68E10, 68R10, 68Q, 05C, 65-01, 65F05, 65F10, 16A78, 90C35, 90C50).
Günter Rote
Heuristics for Graph Coloring
Abstract
Heuristics for Graph Coloring. Some sequential coloring techniques are reviewed. A few general principles for designing heuristics are outlined and recent coloring techniques baaed on tabu search are discussed.
AMS Subject Classification: 05/90.
D. de Werra
Probabilistic Analysis of Graph Algorithms
Abstract
Probabilistic Analysis of Graph Algorithms. We review some of the known results on the average case performance of graph algorithms. The analysis assumes that the problem instances are randomly selected from some reasonable distribution of problems. We consider two types of problem. The first sort is polynomially solvable in the worst case but there are algorithms with better average case performance. In particular we consider the all-pairs shortest path problem, the minimum spanning tree problem, the assignment problem and the cardinality matching problem in sparse graphs. Our second category of problems consists of problems which seem hard in the worst-case but still have algorithms with good average case performance. In particular we consider three NP-Complete problems; the Hamilton cycle problem, the graph bisection problem and graph colouring. In addition we consider the graph isomorphism problem whose exact complexity is still undetermined.
AMS Subject Classifications: 68Q25, 05C8O.
A. M. Frieze
Generating Graphs Uniformly at Random
Abstract
Generating Graphs Uniformly at Random. This paper deals with the problem of sampling from a uniform distribution on various classes of graphs of given size. We consider algorithms and restarting procedures for uniform generation of several kinds of trees, arbitrary unlabelled graphs and various kinds of labelled graphs. Most of the material discussed in this paper has been developed during the last decade by several authors. In section 4.3 some recent results on the generation of outerplanar graphs and maximal planar graphs are presented.
AMS Subject Classification: 05C.
G. Tinhofer
Embedding one Interconnection Network in Another
Abstract
Embedding one Interconnection Network in Another. We review results on embedding network and program structures into popular parallel computer architectures. Such embeddings can be viewed as high level descriptions of efficient methods to simulate an algorithm designed for one type of parallel machine on a different network structure and/or techniques to distribute data/program variables to achieve optimum use of all available processors.
AMS Subject Classifications: 68Q10, 94’02, 94C15.
B. Monien, H. Sudborough
Backmatter
Metadata
Title
Computational Graph Theory
Editors
Prof. Dr. G. Tinhofer
Prof. Dr. E. Mayr
Prof. Dr. H. Noltemeier
Prof. Dr. M. M. Syslo
Copyright Year
1990
Publisher
Springer Vienna
Electronic ISBN
978-3-7091-9076-0
Print ISBN
978-3-211-82177-0
DOI
https://doi.org/10.1007/978-3-7091-9076-0