| Description |
1 online resource (xx, 430 pages) : illustrations |
| Series |
Lecture Notes in Computer Science, 0302-9743 ; 8165 |
|
LNCS sublibrary. SL 1, Theoretical computer science and general issues |
|
Lecture notes in computer science ; 8165. 0302-9743
|
|
LNCS sublibrary. SL 1, Theoretical computer science and general issues.
|
| Contents |
Tree-Like Structures in Graphs: A Metric Point of View / Feodor F. Dragan -- Overview of New Approaches for Approximating TSP / Ola Svensson -- Linear Rank-Width and Linear Clique-Width of Trees / Isolde Adler, Mamadou Moustapha Kanté -- Threshold-Coloring and Unit-Cube Contact Representation of Graphs / Md. Jawaherul Alam, Steven Chaplick -- Rolling Upward Planarity Testing of Strongly Connected Graphs / Christopher Auer, Christian Bachmaier -- Towards a Provably Resilient Scheme for Graph-Based Watermarking / Lucila Maria Souza Bento, Davidson Boccardo -- The Normal Graph Conjecture for Classes of Sparse Graphs / Anne Berry, Annegret Wagler -- On the Parameterized Complexity of Computing Graph Bisections / René van Bevern, Andreas Emil Feldmann -- Fixed-Parameter Tractability and Characterizations of Small Special Treewidth / Hans L. Bodlaender, Stefan Kratsch |
|
880-01 Lower and Upper Bounds for Long Induced Paths in 3-Connected Planar Graphs / Emilio Di Giacomo, Giuseppe Liotta -- Computing Minimum Cycle Bases in Weighted Partial 2-Trees in Linear Time / Carola Doerr, G. Ramakrishna -- Thickness and Colorability of Geometric Graphs / Stephane Durocher, Ellen Gethner -- The Same Upper Bound for Both: The 2-Page and the Rectilinear Crossing Numbers of the n-Cube / Luerbio Faria, Celina M.H. de Figueiredo -- FPT Is Characterized by Useful Obstruction Sets / Michael R. Fellows, Bart M.P. Jansen -- Excluding Graphs as Immersions in Surface Embedded Graphs / Archontia C. Giannopoulou, Marcin Kamiński -- OBDD-Based Representation of Interval Graphs / Marc Gillé -- Tight Upper Bounds for Minimum Feedback Arc Sets of Regular Graphs / Kathrin Hanauer, Franz J. Brandenburg -- A Linear-Time Kernelization for the Rooted k-Leaf Outbranching Problem / Frank Kammer |
|
880-01/(S The θ 5-Graph is a Spanner / Prosenjit Bose, Pat Morin, André van Renssen -- Graphs of Edge-Intersecting Non-splitting Paths in a Tree: Towards Hole Representations / Arman Boyacı, Tınaz Ekim, Mordechai Shalom -- Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs / Hajo Broersma, Jiří Fiala, Petr A. Golovach -- Equilateral L-Contact Graphs / Steven Chaplick, Stephen G. Kobourov -- Parameterized and Approximation Algorithms for the MAF Problem in Multifurcating Trees / Jianer Chen, Jia-Hao Fan, Sing-Hoi Sze -- Linear Separation of Total Dominating Sets in Graphs / Nina Chiarelli, Martin Milanič -- Sparse Square Roots / Manfred Cochefert, Jean-François Couturier -- Completing Colored Graphs to Meet a Target Property / Kathryn Cook, Elaine M. Eschen, R. Sritharan -- Colouring of Graphs with Ramsey-Type Forbidden Subgraphs / Konrad K. Dabrowski, Petr A. Golovach |
|
On Retracts, Absolute Retracts, and Folds in Cographs / Ton Kloks, Yue-Li Wang -- Coloring Triangle-Free Rectangular Frame Intersection Graphs with O(loglogn) Colors / Tomasz Krawczyk, Arkadiusz Pawlik -- On Finding Tucker Submatrices and Lekkerkerker-Boland Subgraphs / Nathan Lindzey, Ross M. McConnell -- Certifying 3-Edge-Connectivity / Kurt Mehlhorn, Adrian Neumann -- Parameterized Algorithms for Max Colorable Induced Subgraph Problem on Perfect Graphs / Neeldhara Misra, Fahad Panolan, Ashutosh Rai -- Characterizing and Computing the Structure of Clique Intersections in Strongly Chordal Graphs / Ragnar Nevries, Christian Rosenke -- Beyond Knights and Knaves / Christine T. Cheng, Andrew McConvey -- Drawing Graphs with Few Arcs / André Schulz -- Connecting Terminals and 2-Disjoint Connected Subgraphs / Jan Arne Telle, Yngve Villanger |
| Summary |
This book constitutes the thoroughly refereed proceedings of the 39th International Workshop on Graph Theoretic Concepts in Computer Science, WG 2013, held in Lubeck, 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 |
| Notes |
Includes author index |
|
Online resource; title from PDF title page (SpringerLink, viewed November 18, 2013) |
| Subject |
Graph theory -- Data processing -- Congresses
|
|
Computer science -- Congresses
|
|
Computers
|
|
Electronic Data Processing
|
|
computers.
|
|
Computer science
|
|
Graph theory -- Data processing
|
| Genre/Form |
proceedings (reports)
|
|
Conference papers and proceedings
|
|
Conference papers and proceedings.
|
|
Actes de congrès.
|
| Form |
Electronic book
|
| Author |
Brandstädt, Andreas, editor
|
|
Jansen, Klaus, editor
|
|
Reischuk, Rüdiger, editor
|
| ISBN |
9783642450433 |
|
3642450431 |
|
3642450423 |
|
9783642450426 |
|
