Luca Cittadini, Giuseppe Di Battista, Massimo Rimondini (auth.), Hajo Broersma, Thomas Erlebach, Tom Friedetzky, Daniel Paulusma (eds.)3540922474, 9783540922476
This book constitutes the thoroughly refereed post-conference proceedings of the 34th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2008, held in Durham, UK, in June/July 2008.
The 30 revised full papers presented together with 3 invited paper were carefully reviewed and selected from 76 submissions. The papers feature original results on all aspects of graph-theoretic concepts in Computer Science, e.g. structural graph theory, sequential, parallel, and distributed graph and network algorithms and their complexity, graph grammars and graph rewriting systems, graph-based modeling, graph-drawing and layout, diagram methods, and support of these concepts by suitable implementations.
Table of contents :
Front Matter….Pages –
(Un)-Stable Routing in the Internet: A Survey from the Algorithmic Perspective….Pages 1-13
Memory Efficient Anonymous Graph Exploration….Pages 14-29
Algorithmic Meta Theorems….Pages 30-30
A Most General Edge Elimination Polynomial….Pages 31-42
Approximating the Metric TSP in Linear Time….Pages 43-54
The Valve Location Problem in Simple Network Topologies….Pages 55-65
A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs….Pages 66-77
On the Pseudo-achromatic Number Problem….Pages 78-89
Making Role Assignment Feasible: A Polynomial-Time Algorithm for Computing Ecological Colorings….Pages 90-100
Faster Exact Bandwidth….Pages 101-109
Additive Spanners for Circle Graphs and Polygonal Graphs….Pages 110-121
Upward Straight-Line Embeddings of Directed Graphs into Point Sets….Pages 122-133
Complexity of the Packing Coloring Problem for Trees….Pages 134-145
Characterizations of Restricted Pairs of Planar Graphs Allowing Simultaneous Embedding with Fixed Edges….Pages 146-158
A Lower Bound on the Area Requirements of Series-Parallel Graphs….Pages 159-170
On Independent Sets and Bicliques in Graphs….Pages 171-182
Evaluations of Graph Polynomials….Pages 183-194
Parameterized Complexity for Domination Problems on Degenerate Graphs….Pages 195-205
An Algorithm for Finding Input-Output Constrained Convex Sets in an Acyclic Digraph….Pages 206-217
Cutwidth of Split Graphs, Threshold Graphs, and Proper Interval Graphs….Pages 218-229
The Rank-Width of the Square Grid….Pages 230-239
Improved Upper Bounds for Partial Vertex Cover….Pages 240-251
On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width….Pages 252-263
Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms….Pages 264-274
What Is between Chordal and Weakly Chordal Graphs?….Pages 275-286
Parameterized Graph Cleaning Problems….Pages 287-299
Traffic Grooming in Unidirectional WDM Rings with Bounded Degree Request Graph….Pages 300-311
Fast Robber in Planar Graphs….Pages 312-323
From a Circular-Arc Model to a Proper Circular-Arc Model….Pages 324-335
Digraph Decompositions and Monotonicity in Digraph Searching….Pages 336-347
Searching for a Visible, Lazy Fugitive….Pages 348-359
A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes….Pages 360-371
Local Construction and Coloring of Spanners of Location Aware Unit Disk Graphs….Pages 372-383
Back Matter….Pages –
Reviews
There are no reviews yet.