Graph-Theoretic Concepts in Computer Science

Table of Contents

1. Altmetric Badge
   Book Overview
2. Altmetric Badge
   Chapter 36 Near-optimal dominating sets in dense random graphs in polynomial expected time
3. Altmetric Badge
   Chapter 37 Approximating minimum weight perfect matchings for complete graphs satisfying the triangle inequality
4. Altmetric Badge
   Chapter 38 Hierarchically specified unit disk graphs
5. Altmetric Badge
   Chapter 39 Bounded tree-width and LOGCFL
6. Altmetric Badge
   Chapter 40 On reduction algorithms for graphs with small treewidth
7. Altmetric Badge
   Chapter 41 Algorithms and complexity of sandwich problems in graphs (extended abstract)
8. Altmetric Badge
   Chapter 42 On-line graph algorithms for incremental compilation
9. Altmetric Badge
   Chapter 43 Average case analysis of fully dynamic connectivity for directed graphs
10. Altmetric Badge
    Chapter 44 Fully dynamic maintenance of vertex cover
11. Altmetric Badge
    Chapter 45 Dynamic algorithms for graphs with treewidth 2
12. Altmetric Badge
    Chapter 46 Short disjoint cycles in graphs with degree constraints
13. Altmetric Badge
    Chapter 47 Efficient algorithms for tripartitioning triconnected graphs and 3-edge-connected graphs
14. Altmetric Badge
    Chapter 48 Towards a solution of the Holyer's problem
15. Altmetric Badge
    Chapter 49 Graphs, hypergraphs and hashing
16. Altmetric Badge
    Chapter 50 Coloring k -colorable graphs in constant expected parallel time
17. Altmetric Badge
    Chapter 51 Deciding 3-colourability in less than O (1.415 n ) steps
18. Altmetric Badge
    Chapter 52 A rainbow about T -colorings for complete graphs
19. Altmetric Badge
    Chapter 53 Approximating the chromatic polynomial of a graph
20. Altmetric Badge
    Chapter 54 Asteroidal triple-free graphs
21. Altmetric Badge
    Chapter 55 The parallel complexity of elimination ordering procedures
22. Altmetric Badge
    Chapter 56 Dually chordal graphs
23. Altmetric Badge
    Chapter 57 The size of reduced OBDDs and optimal read-once branching programs for almost all Boolean functions
24. Altmetric Badge
    Chapter 58 Regular marked Petri nets
25. Altmetric Badge
    Chapter 59 The asynchronous committee meeting problem
26. Altmetric Badge
    Chapter 60 Gossiping in vertex-disjoint paths mode in interconnection networks
27. Altmetric Badge
    Chapter 61 The folded Petersen network: A new versatile multiprocessor interconnection topology
28. Altmetric Badge
    Chapter 62 Fast load balancing in Cayley graphs and in circuits
29. Altmetric Badge
    Chapter 63 Concurrent flows and packet routing in Cayley graphs (Preliminary version)
30. Altmetric Badge
    Chapter 64 On multi-label linear interval routing schemes
31. Altmetric Badge
    Chapter 65 An ‘All pairs shortest paths’ distributed algorithm using 2 n 2 messages
32. Altmetric Badge
    Chapter 66 Linear layouts of generalized hypercubes
33. Altmetric Badge
    Chapter 67 Graph ear decompositions and graph embeddings
34. Altmetric Badge
    Chapter 68 Improved bounds for the crossing numbers on surfaces of genus g
35. Altmetric Badge
    Chapter 69 Two algorithms for finding rectangular duals of planar graphs
36. Altmetric Badge
    Chapter 70 A more compact visibility representation