Graph-Theoretic Concepts in Computer Science [electronic resource] : 34th International Workshop, WG 2008, Durham, UK, June 30 -- July 2, 2008, Revised Papers / edited by Hajo Broersma, Thomas Erlebach, Tom Friedetzky, Daniel Paulusma.

Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2008.
1 online resource (XIII, 386 pages)
1st ed. 2008.
Computer Science (Springer-11645)
LNCS sublibrary. Theoretical computer science and general issues SL 1, 5344
Theoretical Computer Science and General Issues ; 5344
Contained In:
Springer eBooks

Location Notes Your Loan Policy


Computer science-Mathematics.
Numerical analysis.
Data structures (Computer science).
Computer graphics.
Local subjects:
Algorithm Analysis and Problem Complexity. (search)
Discrete Mathematics in Computer Science. (search)
Numeric Computing. (search)
Data Structures. (search)
Computer Graphics. (search)
Algorithms. (search)
System Details:
text file PDF
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.
Invited Contributions
(Un)-Stable Routing in the Internet: A Survey from the Algorithmic Perspective
Memory Efficient Anonymous Graph Exploration
Algorithmic Meta Theorems
Regular Papers
A Most General Edge Elimination Polynomial
Approximating the Metric TSP in Linear Time
The Valve Location Problem in Simple Network Topologies
A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs
On the Pseudo-achromatic Number Problem
Making Role Assignment Feasible: A Polynomial-Time Algorithm for Computing Ecological Colorings
Faster Exact Bandwidth
Additive Spanners for Circle Graphs and Polygonal Graphs
Upward Straight-Line Embeddings of Directed Graphs into Point Sets
Complexity of the Packing Coloring Problem for Trees
Characterizations of Restricted Pairs of Planar Graphs Allowing Simultaneous Embedding with Fixed Edges
A Lower Bound on the Area Requirements of Series-Parallel Graphs
On Independent Sets and Bicliques in Graphs
Evaluations of Graph Polynomials
Parameterized Complexity for Domination Problems on Degenerate Graphs
An Algorithm for Finding Input-Output Constrained Convex Sets in an Acyclic Digraph
Cutwidth of Split Graphs, Threshold Graphs, and Proper Interval Graphs
The Rank-Width of the Square Grid
Improved Upper Bounds for Partial Vertex Cover
On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width
Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms
What Is between Chordal and Weakly Chordal Graphs?
Parameterized Graph Cleaning Problems
Traffic Grooming in Unidirectional WDM Rings with Bounded Degree Request Graph
Fast Robber in Planar Graphs
From a Circular-Arc Model to a Proper Circular-Arc Model
Digraph Decompositions and Monotonicity in Digraph Searching
Searching for a Visible, Lazy Fugitive
A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes
Local Construction and Coloring of Spanners of Location Aware Unit Disk Graphs.
Broersma, Hajo. editor., Editor,
Erlebach, Thomas. editor., Editor,
Friedetzky, Tom. editor., Editor,
Paulusma, Danièˆl, editor., Editor,
SpringerLink (Online service)
Other format:
Printed edition:
Printed edition:
Publisher Number:
10.1007/978-3-540-92248-3 doi
Access Restriction:
Restricted for use by site license.