Graph-Theoretic Concepts in Computer Science

1. Front Matter

   PDF

2. Near-optimal dominating sets in dense random graphs in polynomial expected time

   • Sotiris E. Nikoletseas, Paul G. Spirakis

   Pages 1-10

3. Approximating minimum weight perfect matchings for complete graphs satisfying the triangle inequality

   • N. W. Holloway, S. Ravindran, A. M. Gibbons

   Pages 11-20

4. Hierarchically specified unit disk graphs

   • M. V. Marathe, V. Radhakrishnan, H. B. Hunt III, S. S. Ravi

   Pages 21-32

5. Bounded tree-width and LOGCFL

   • Egon Wanke

   Pages 33-44

6. On reduction algorithms for graphs with small treewidth

   • Hans L. Bodlaender

   Pages 45-56

7. Algorithms and complexity of sandwich problems in graphs (extended abstract)

   • Martin Charles Golumbic, Haim Kaplan, Ron Shamir

   Pages 57-69

8. On-line graph algorithms for incremental compilation

   • Alberto Marchetti-Spaccamela, Umberto Nanni, Hans Rohnert

   Pages 70-86

9. Average case analysis of fully dynamic connectivity for directed graphs

   • Paola Alimonti, Stefano Leonardi, Alberto Marchetti-Spacccamela, Xavier Messeguer

   Pages 87-98

10. Fully dynamic maintenance of vertex cover

    • Zoran Ivković, Errol L. Lloyd

    Pages 99-111

11. Dynamic algorithms for graphs with treewidth 2

    • Hans L. Bodlaender

    Pages 112-124

12. Short disjoint cycles in graphs with degree constraints

    • Andreas Brandstädt, Heinz-Jürgen Voss

    Pages 125-131

13. Efficient algorithms for tripartitioning triconnected graphs and 3-edge-connected graphs

    • Koichi Wada, Kimio Kawaguchi

    Pages 132-143

14. Towards a solution of the Holyer's problem

    • Zbigniew Lonc

    Pages 144-152

15. Graphs, hypergraphs and hashing

    • George Havas, Bohdan S. Majewski, Nicholas C. Wormald, Zbigniew J. Czech

    Pages 153-165

16. Coloring k-colorable graphs in constant expected parallel time

    • Luděk Kučera

    Pages 166-176

17. Deciding 3-colourability in less than O(1.415ⁿ) steps

    • Ingo Schiermeyer

    Pages 177-188

18. A rainbow about T-colorings for complete graphs

    • Klaus Jansen

    Pages 189-199

19. Approximating the chromatic polynomial of a graph

    • Nai-Wei Lin

    Pages 200-210

20. Asteroidal triple-free graphs

    • Derek. G. Corneil, Stephan Olariu, Lorna Stewart

    Pages 211-224

This volume contains the proceedings of the 19th International Workshop on Graph-Theoretic Concepts in Computer Science, WG '93, held near Utrecht, The Netherlands, in 1993.
The papers are grouped into parts on: hard problems on classes of graphs, structural graph theory, dynamic graph algorithms, structure-oriented graph algorithms, graph coloring, AT-free and chordal graphs, circuits and nets, graphs and interconnection networks, routing and shortest paths, and graph embedding and layout.
The 35 revised papers were chosen from 92 submissions after a careful refereeing process.

• Graph
• Graph-Algorithmen
• Kombinatorische Algorithmen
• Layout
• algorithm
• algorithms
• combinatorial algorithms
• distributed algorithms
• graph algorithms
• graph theory
• network theory
• algorithm analysis and problem complexity
• combinatorics

Policies and ethics