𝔖 Scriptorium
✦   LIBER   ✦
📁

Graph-Theoretic Concepts in Computer Science: 39th International Workshop, WG 2013, Lübeck, Germany, June 19-21, 2013, Revised Papers

✍ Scribed by Feodor F. Dragan (auth.), Andreas Brandstädt, Klaus Jansen, Rüdiger Reischuk (eds.)

Publisher
Springer-Verlag Berlin Heidelberg
Year
2013
Tongue
English
Leaves
446
Series
Lecture Notes in Computer Science 8165 Theoretical Computer Science and General Issues
Edition
1
Category
Library
⬇  Acquire This Volume

No coin nor oath required. For personal study only.

✦ Synopsis

This book constitutes the thoroughly refereed proceedings of the 39th International Workshop on Graph Theoretic Concepts in Computer Science, WG 2013, held in Lübeck, Germany, in June 2013. The 34 revised full papers presented were carefully reviewed and selected from 61 submissions. The book also includes two abstracts. The papers cover a wide range of topics in graph theory related to computer science, such as structural graph theory with algorithmic or complexity applications; design and analysis of sequential, parallel, randomized, parameterized and distributed graph and network algorithms; computational complexity of graph and network problems; computational geometry; graph grammars, graph rewriting systems and graph modeling; graph drawing and layouts; random graphs and models of the web and scale-free networks; and support of these concepts by suitable implementations and applications.

✦ Table of Contents

Front Matter....Pages -
Tree-Like Structures in Graphs: A Metric Point of View....Pages 1-4
Overview of New Approaches for Approximating TSP....Pages 5-11
Linear Rank-Width and Linear Clique-Width of Trees....Pages 12-25
Threshold-Coloring and Unit-Cube Contact Representation of Graphs....Pages 26-37
Rolling Upward Planarity Testing of Strongly Connected Graphs....Pages 38-49
Towards a Provably Resilient Scheme for Graph-Based Watermarking....Pages 50-63
The Normal Graph Conjecture for Classes of Sparse Graphs....Pages 64-75
On the Parameterized Complexity of Computing Graph Bisections....Pages 76-87
Fixed-Parameter Tractability and Characterizations of Small Special Treewidth....Pages 88-99
The θ 5 -Graph is a Spanner....Pages 100-114
Graphs of Edge-Intersecting Non-splitting Paths in a Tree: Towards Hole Representations....Pages 115-126
Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs....Pages 127-138
Equilateral L-Contact Graphs....Pages 139-151
Parameterized and Approximation Algorithms for the MAF Problem in Multifurcating Trees....Pages 152-164
Linear Separation of Total Dominating Sets in Graphs....Pages 165-176
Sparse Square Roots....Pages 177-188
Completing Colored Graphs to Meet a Target Property....Pages 189-200
Colouring of Graphs with Ramsey-Type Forbidden Subgraphs....Pages 201-212
Lower and Upper Bounds for Long Induced Paths in 3-Connected Planar Graphs....Pages 213-224
Computing Minimum Cycle Bases in Weighted Partial 2-Trees in Linear Time....Pages 225-236
Thickness and Colorability of Geometric Graphs....Pages 237-248
The Same Upper Bound for Both: The 2-Page and the Rectilinear Crossing Numbers of the n -Cube....Pages 249-260
FPT Is Characterized by Useful Obstruction Sets....Pages 261-273
Excluding Graphs as Immersions in Surface Embedded Graphs....Pages 274-285
OBDD-Based Representation of Interval Graphs....Pages 286-297
Tight Upper Bounds for Minimum Feedback Arc Sets of Regular Graphs....Pages 298-309
A Linear-Time Kernelization for the Rooted k -Leaf Outbranching Problem....Pages 310-320
On Retracts, Absolute Retracts, and Folds in Cographs....Pages 321-332
Coloring Triangle-Free Rectangular Frame Intersection Graphs with O (loglog n ) Colors....Pages 333-344
On Finding Tucker Submatrices and Lekkerkerker-Boland Subgraphs....Pages 345-357
Certifying 3-Edge-Connectivity....Pages 358-369
Parameterized Algorithms for Max Colorable Induced Subgraph Problem on Perfect Graphs....Pages 370-381
Characterizing and Computing the Structure of Clique Intersections in Strongly Chordal Graphs....Pages 382-393
Beyond Knights and Knaves....Pages 394-405
Drawing Graphs with Few Arcs....Pages 406-417
Connecting Terminals and 2-Disjoint Connected Subgraphs....Pages 418-428
Back Matter....Pages -

✦ Subjects

Discrete Mathematics in Computer Science; Algorithm Analysis and Problem Complexity; Data Structures; Geometry; Algorithms

📜 SIMILAR VOLUMES

Graph-Theoretic Concepts in Computer Sci
📁 Graph-Theoretic Concepts in Computer Science: 29th International Workshop, WG 2003. Elspeet, The Netherlands, June 19-21, 2003. Revised Papers
✍ Michael R. Fellows (auth.), Hans L. Bodlaender (eds.) 📂 Library 📅 2003 🏛 Springer-Verlag Berlin Heidelberg 🌐 English

<p>The 29th International Workshop on Graph-Theoretic Concepts in Computer Science(WG2003)washeldintheMennorodeconferenceCenterinElspeet,The Netherlands.TheworkshopwasorganizedbytheCenterforAlgorithmicSystems of the Institute of Information and Computing Sciences of Utrecht University. The workshop

Graph-Theoretic Concepts in Computer Sci
📁 Graph-Theoretic Concepts in Computer Science: 29th International Workshop, WG 2003. Elspeet, The Netherlands, June 19-21, 2003. Revised Papers
✍ Michael R. Fellows (auth.), Hans L. Bodlaender (eds.) 📂 Library 📅 2003 🏛 Springer-Verlag Berlin Heidelberg 🌐 English

<p>The 29th International Workshop on Graph-Theoretic Concepts in Computer Science(WG2003)washeldintheMennorodeconferenceCenterinElspeet,The Netherlands.TheworkshopwasorganizedbytheCenterforAlgorithmicSystems of the Institute of Information and Computing Sciences of Utrecht University. The workshop

Graph-Theoretic Concepts in Computer Sci
📁 Graph-Theoretic Concepts in Computer Science: 41st International Workshop, WG 2015, Garching, Germany, June 17-19, 2015, Revised Papers
✍ Ernst W. Mayr (eds.) 📂 Library 📅 2016 🏛 Springer-Verlag Berlin Heidelberg 🌐 English

<p><p>This book constitutes revised selected papers from the 41<sup>st</sup> International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2015, held in Garching, Germany, in June 2015. <br> The 32 papers presented in this volume were carefully reviewed and selected from 79 submissions.

Graph-Theoretic Concepts in Computer Sci
📁 Graph-Theoretic Concepts in Computer Science: 45th International Workshop, WG 2019, Vall de Núria, Spain, June 19–21, 2019, Revised Papers
✍ Ignasi Sau, Dimitrios M. Thilikos 📂 Library 📅 2019 🏛 Springer International Publishing 🌐 English

<p><p>This book constitutes the revised papers of the 45th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2019, held in Vall de Núria, Spain, in June 2019.</p><p>The 29 full papers presented in this volume were carefully reviewed and selected from 87 submissions. They cov

Graph-Theoretic Concepts in Computer Sci
📁 Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004. Revised Papers
✍ Derek G. Corneil (auth.), Juraj Hromkovič, Manfred Nagl, Bernhard Westfechtel (e 📂 Library 📅 2005 🏛 Springer-Verlag Berlin Heidelberg 🌐 English

<p>During its 30-year existence, the International Workshop on Graph-Theoretic Concepts in Computer Science has become a distinguished and high-quality computer science event. The workshop aims at uniting theory and practice by demonstrating how graph-theoretic concepts can successfully be applied t

Graph-Theoretic Concepts in Computer Sci
📁 Graph-Theoretic Concepts in Computer Science: 37th International Workshop, WG 2011, Teplá Monastery, Czech Republic, June 21-24, 2011. Revised Papers
✍ Alberto Marchetti-Spaccamela (auth.), Petr Kolman, Jan Kratochvíl (eds.) 📂 Library 📅 2011 🏛 Springer-Verlag Berlin Heidelberg 🌐 English

<p>This book constitutes the revised selected papers of the 37th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2011, held at Teplá Monastery, Czech Republic, in June 2011.<br>The 28 revised papers presented were carefully reviewed and selected from 52 submissions. The wo