Graph-Theoretic Concepts in Computer Science

1. Front Matter

   PDF

2. Gadgets, approximation, and linear programming: Improved hardness results for cut and satisfiability problems

   • David P. Williamson

   Pages 1-1

3. Non-oblivious local search for MAX 2-CCSP with application to MAX DICUT

   • Paola Alimonti

   Pages 2-14

4. On the number of simple cycles in planar graphs

   • Helmut Alt, Ulrich Fuchs, Klaus Kriegel

   Pages 15-24

5. On the separable-homogeneous decomposition of graphs

   • Luitpold Babel, Stephan Olariu

   Pages 25-37

6. Pseudo-hamiltonian graphs

   • Luitpold Babel, Gerhard J. Woeginger

   Pages 38-51

7. Acyclic orientations for deadlock prevention in interconnection networks

   • Jean-Claude Bermond, Miriam Di Ianni, Michele Flammini, Stephane Perennes

   Pages 52-64

8. Weak-order extensions of an order

   • Karell Bertet, Jens Gustedt, Michel Morvan

   Pages 65-77

9. An upper bound for the maximum cut mean value

   • Alberto Bertoni, Paola Campadelli, Roberto Posenato

   Pages 78-84

10. NP-completeness results for minimum planar spanners

    • Ulrik Brandes, Dagmar Handke

    Pages 85-99

11. Computing the independence number of dense triangle-free graphs

    • Stephan Brandt

    Pages 100-108

12. Algorithms for the treewidth and minimum fill-in of HHD-free graphs

    • H. J. Broersma, E. Dahlhaus, T. Kloks

    Pages 109-117

13. Block decomposition of inheritance hierarchies

    • Christian Capelle

    Pages 118-131

14. Minimal elimination ordering inside a given chordal graph

    • Dias Dahlhaus

    Pages 132-143

15. On-line algorithms for networks of temporal constraints

    • Fabrizio d'Amore, Fabio Iacobini

    Pages 144-156

16. Parallel algorithms for treewidth two

    • Babette de Fluiter, Hans L. Bodlaender

    Pages 157-170

17. On optimal graphs embedded into paths and rings, with analysis using l ₁-spheres

    • Yefim Dinitz, Marcelo Feighelstein, Shmuel Zaks

    Pages 171-183

18. On greedy matching ordering and greedy matchable graphs

    • Feodor F. Dragan

    Pages 184-198

19. Off-line and on-line call-scheduling in stars and trees

    • Thomas Erlebach, Klaus Jansen

    Pages 199-213

20. Computational complexity of the Krausz dimension of graphs

    • Petr Hliněný, Jan Kratochvíl

    Pages 214-228

This book constitutes the strictly refereed post-workshop proceedings of the 23rd International Workshop on Graph-Theoretic Concepts in Computer Science, WG'97, held in Berlin, Germany in June 1997.
The volume presents 28 revised full papers carefully selected for inclusion in the book from 42 submissions. The papers address a variety of graph-theoretic issues relevant from the computer science point of view such as graph algorithms, cycles, graph decompositions, interconnection networks, local search, graph orderings, graph matching, graph languages, tree-width computation, etc.

• Algorithms
• Graph
• Matching
• Sim
• algorithm
• complexity
• computer
• computer science
• programming
• sets
• algorithm analysis and problem complexity
• data structures
• combinatorics

Policies and ethics