05968nam 22008655 450 99646636790331620230223032125.03-540-92248-210.1007/978-3-540-92248-3(CKB)1000000000545815(SSID)ssj0000317989(PQKBManifestationID)11230730(PQKBTitleCode)TC0000317989(PQKBWorkID)10294006(PQKB)11185901(DE-He213)978-3-540-92248-3(MiAaPQ)EBC3063788(MiAaPQ)EBC6281820(PPN)132861852(EXLCZ)99100000000054581520100301d2008 u| 0engurnn|008mamaatxtccrGraph-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 Paulusma1st ed. 2008.Berlin, Heidelberg :Springer Berlin Heidelberg :Imprint: Springer,2008.1 online resource (XIII, 386 p.) Theoretical Computer Science and General Issues,2512-2029 ;5344Proceedings of the "34th International Workshop, WG 2008, Durham, UK, June 30-July 2, 2008".3-540-92247-4 Includes bibliographical references and index.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.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.Theoretical Computer Science and General Issues,2512-2029 ;5344AlgorithmsComputer science—MathematicsDiscrete mathematicsNumerical analysisArtificial intelligence—Data processingComputer graphicsAlgorithmsDiscrete Mathematics in Computer ScienceNumerical AnalysisData ScienceComputer GraphicsAlgorithms.Computer science—Mathematics.Discrete mathematics.Numerical analysis.Artificial intelligence—Data processing.Computer graphics.Algorithms.Discrete Mathematics in Computer Science.Numerical Analysis.Data Science.Computer Graphics.004.015115DAT 537fstubMAT 055fstubSS 4800rvkBroersma Hajoedthttp://id.loc.gov/vocabulary/relators/edtErlebach Thomasedthttp://id.loc.gov/vocabulary/relators/edtFriedetzky Tomedthttp://id.loc.gov/vocabulary/relators/edtPaulusma Danieledthttp://id.loc.gov/vocabulary/relators/edtConference on Graphtheoretic Concepts in Computer Science (34th : 2008 : Durham, UK).MiAaPQMiAaPQMiAaPQBOOK996466367903316Graph-Theoretic Concepts in Computer Science2569248UNISA