Graph-Theoretic Concepts in Computer Science: 34th International Workshop, WG 2008, Durham, UK, June 30 -- July 2, 2008, Revised Papers / Edition 1

by Hajo Broersma, Thomas Erlebach, Tom Friedetzky, Daniel Paulusma

Overview

The 34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2008) took place in Van Mildert College at Durham University, UK, 30 June – 2 July 2008. The approximately 80 participants came from va- ous countries all over the world, among them Australia, Brazil, Canada, Chile, Czech Republic, France, Greece, Hungary,Israel, Italy, Japan, The Netherlands, Norway, Poland, Spain, Switzerland, UK and the USA. WG 2008 continued the series of 33 previous WG conferences. Since 1975, the WG conference has taken place 21 times in Germany, four times in The Netherlands, twice in Austria as well as once in Italy, Slovakia, Switzerland, the Czech Republic, France, Norway and now in the UK. The WG conference traditionally aims at uniting theory and practice by demonstrating how graph-theoretic concepts can be applied to various areas in computer science, or by extracting new problems from applications. The goal is to present recent research results and to identify and explore directions of future research. The continuing interest in the WG conferences was reffected in the number and quality of submissions; 76 papers were submitted and in an evaluation process with four reports per submission, 30 papers were accepted by the Program Committee for the conference. Due to the high number of submissions and the limited schedule of 3 days, various good papers could not be accepted. There were excellent invited talks by Giuseppe Di Battista(UniversitàRoma Tre, Italy) on algorithmic aspects of (un)-stable routing in the Internet, by Leszek Gąsieniec (University of Liverpool, UK) on memory-efficient graph exploration, and by Martin Grohe (Humboldt-Universitä tzu Berlin, Germany) on algorithmic meta theorems.

Product Details

ISBN-13:	9783540922476
Publisher:	Springer Berlin Heidelberg
Publication date:	02/13/2009
Series:	Lecture Notes in Computer Science , #5344
Edition description:	2008
Pages:	386
Product dimensions:	6.10(w) x 9.30(h) x 0.90(d)

Table of Contents

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.- DigraphDecompositions 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.