Graph-Theoretic Concepts in Computer Science

1. Front Matter

   PDF

2. Disjoint paths in the hypercube

   • Seshu Madhavapeddy, I. Hal Sudborough

   Pages 3-18

3. Time bounds for broadcasting in bounded degree graphs

   • Renato M. Capocelli, Luisa Gargano, Ugo Vaccaro

   Pages 19-33

4. t/s-Diagnosable systems: A characterization and diagnosis algorithm

   • A. Das, K. Thulasiraman, V. K. Agarwal, K. B. Lakshmanan

   Pages 34-45

5. Toward a complete representation of graphoids in graphs — Abridged Version

   • Robert Y. Geva, Azaria Paz

   Pages 46-62

6. CADULA — A graph-based model for monitoring CAD-processes

   • Detlev Ruland

   Pages 63-77

7. On hyperedge replacement and BNLC graph grammars

   • Walter Vogler

   Pages 78-93

8. Graph rewriting systems with priorities

   • Michel Billaud, Pierre Lafon, Yves Metivier, Eric Sopena

   Pages 94-106

9. Filtering hyperedge-replacement languages through compatible properties

   • Annegret Habel, Hans-Jörg Kreowski

   Pages 107-120

10. Describing distributed systems by categorical graph grammars

    • H. J. Schneider

    Pages 121-135

11. A parser for context free plex grammars

    • H. Bunke, B. Haller

    Pages 136-150

12. Introduction to PROGRESS, an attribute graph grammar based specification language

    • Andy Schürr

    Pages 151-165

13. On the complexity of optimal drawings of graphs

    • Franz J. Brandenburg

    Pages 166-180

14. Bounds to the page number of partially ordered sets

    • Maciej M. Sysło

    Pages 181-195

15. Beyond Steiner's problem: A VLSI oriented generalization

    • Gabriele Reich, Peter Widmayer

    Pages 196-210

16. A fast sequential and parallel algorithm for the computation of the k-closure of a graph

    • Ingo Schiermeyer

    Pages 211-217

17. On feedback problems in digraphs

    • Ewald Speckenmeyer

    Pages 218-231

18. Improved self-reduction algorithms for graphs with bounded treewidth

    • Hans L. Bodlaender

    Pages 232-244

19. Finding a minimal transitive reduction in a strongly connected digraph within linear time

    • Klaus Simon

    Pages 245-259

20. Paging binary trees with external balancing

    • Andreas Henrich, Hans-Werner Six, Peter Widmayer

    Pages 260-276

The aim of this workshop series is to contribute to integration in computer science by applying graph-theoretic concepts. Commonalities between various fields of specialization in computer science may be detected by applying graph-theoretic concepts. The workshops are unusual in that they combine theoretical aspects with practice and applications. Applications dealt with in this volume include the use of graph-theoretic concepts in distributed and parallel computation, VLSI, CAD, software engineering, computer graphics, data structures, and computational geometry.

• Action
• Algorithms
• Digraph
• Graph
• Graph theory
• Sim
• VLSI
• algorithm
• complexity
• data structure
• data structures
• distributed systems
• modeling
• processor
• software engineering
• combinatorics
• algorithm analysis and problem complexity

Policies and ethics