Graph-Theoretic Concepts in Computer Science: 24th International Workshop, WG’98, Smolenice Castle, Slovak Republic, June 18-20, 1998. Proceedings

B. Courcelle, J. A. Makowsky, U. Rotics (auth.), Juraj Hromkovič, Ondrej Sýkora (eds.)3540651950, 9783540651956

This book constitutes the thoroughly refereed post-workshop proceedings of the 24th International Workshop on Graph-Theoretic Concepts in Computer Science, WG’98, held in Smolenice Castle, Slovak Republic, in June 1998.
The 30 revised full papers presented were carefully selected from a total of 61 submissions. The papers provide a wealth of new results for various classes of graphs, graph computations, graph algorithms and graph-theoretic applications in computer science.

---

Table of contents :
Front Matter….Pages –
Linear Time Solvable Optimization Problems on Graphs of Bounded Clique Width….Pages 1-16
Minus Domination in Small-Degree Graphs….Pages 17-25
The Vertex-Disjoint Triangles Problem….Pages 26-37
Communication in the Two-Way Listen-in Vertex-Disjoint Paths Mode….Pages 38-49
Broadcasting on Anonymous Unoriented Tori….Pages 50-62
Families of Graphs Having Broadcasting and Gossiping Properties….Pages 63-77
Optical All-to-All Communication in Inflated Networks….Pages 78-87
A Generalization of AT-free Graphs and a Generic Algorithm for Solving Treewidth, Minimum Fill-In and Vertex Ranking….Pages 88-99
A Polynomial-Time Algorithm for Finding Total Colorings of Partial k -Trees….Pages 100-113
Rankings of Directed Graphs….Pages 114-123
Drawing Planar Partitions II: HH-Drawings….Pages 124-136
Triangles in Euclidean Arrangements….Pages 137-148
Internally Typed Second-Order Term Graphs….Pages 149-163
Compact Implicit Representation of Graphs….Pages 164-176
Graphs with Bounded Induced Distance….Pages 177-191
Diameter Determination on Restricted Graph Families….Pages 192-202
Independent Tree Spanners….Pages 203-214
Upgrading Bottleneck Constrained Forests….Pages 215-226
Routing in Recursive Circulant Graphs: Edge Forwarding Index and Hamiltonian Decomposition….Pages 227-241
Improved Compressions of Cube-Connected Cycles Networks….Pages 242-256
Efficient Embeddings of Grids into Grids….Pages 257-271
Integral Uniform Flows in Symmetric Networks….Pages 272-284
Splitting Number is NP-Complete….Pages 285-297
Tree Spanners in Planar Graphs….Pages 298-309
A Linear-Time Algorithm to Find Four Independent Spanning Trees in Four-Connected Planar Graphs….Pages 310-323
Linear Algorithms for a k -partition Problem of Planar Graphs without Specifying Bases….Pages 324-336
Domination and Steiner Tree Problems on Graphs with Few P 4 s….Pages 337-350
Minimum Fill-In and Treewidth for Graphs Modularly Decomposable into Chordal Graphs….Pages 351-358
Interval Completion with the Smallest Max-Degree….Pages 359-371
An Estimate of the Tree-Width of a Planar Graph Which Has Not a Given Planar Grid as a Minor…..Pages 372-383
Back Matter….Pages –