Amazon cover image
Image from Amazon.com

Graph-theoretic concepts in computer science : 37th International Workshop, WG 2011, Teplá Monastery, Czech Republic, June 21-24, 2011 : revised papers / Petr Kolman, Jan Kratochvíl (eds.).

By: Contributor(s): Material type: TextTextSeries: Lecture notes in computer science ; 6986. | Lecture notes in computer science. Advanced research in computing and software science.Publication details: Heidelberg ; New York : Springer-Verlag, ©2011.Description: 1 online resource (xi, 344 pages) : illustrations (some color)Content type:
  • text
Media type:
  • computer
Carrier type:
  • online resource
ISBN:
  • 9783642258701
  • 3642258700
  • 3642258697
  • 9783642258695
Subject(s): Genre/Form: Additional physical formats: Printed edition:: No titleDDC classification:
  • 511/.5 23
LOC classification:
  • QA166 .C664 2011
Online resources:
Contents:
Intro; Title page; Preface; Organization; Table of Contents; Structures and Hyperstructures in Metabolic Networks; Introduction; Structural Characterization; Dynamic Characterization; References; Important Separators and Parameterized Algorithms; Introduction; Multiway Cut; Directed Graphs; Conclusions; References; Split Clique Graph Complexity; Introduction; NP-Complete Split Clique Graph Classes; Polynomially Solvable Split Clique Graph Classes; Open Related Problems; References; On Searching for Small Kochen-Specker Vector Systems; Introduction; Kochen-Specker Vector Systems; Embeddability
Lower BoundsConclusion; References; Characterizations of Deque and Queue Graphs; Introduction; Preliminaries; Deque Graphs; Characterizing Deque Graphs; Hamiltonian Paths in Deque and Queue Graphs; Deciding If a Graph Is a Deque Graph Is NP-Complete; Queue Graphs; Conclusion; References; Graph Classes with Structured Neighborhoods and Algorithmic Applications; Introduction; Framework; Upper Bounds on Boolean-Width of Graph Classes; Vertex Partitioning Problems; Lower Bounds; Conclusion; References; Exact Algorithms for Kayles; Introduction; Preliminaries
An Upper Bound on the Number of K-setsA Bound on the Number of K-sets in Trees; The Exact Algorithm; Lower Bounds; Conclusions; References; The Cinderella Game on Holes and Anti-holes; Introduction; Definitions and First Results; The Game on General Graphs; The Game on Holes; Proof of the Upper Bound for GREEDY; Proof of the Lower Bound for GREEDY; The Game on Anti-holes; Conclusions and Conjectures; References; On the Complexity of Planar Covering of Small Graphs; Introduction; Hardness of Planar Covering of K_6; Hardness of Planar Covering of K_4, K_5, K_4+ and K_5-
Hardness of Planar Covering of the Dumbbell GraphConclusions; References; Approximability of Economic Equilibrium for Housing Markets with Duplicate Houses; Introduction; Preliminaries; Bounds for sat(M); Inapproximability; The Transformation; Inapproximability for Max-SHDTri; Inapproximability for Max-SHDTies; Conclusion and Open Problems; References; Planarization and Acyclic Colorings of Subcubic Claw-Free Graphs; Introduction; Preliminaries and Definitions; Simplifying the Graph; Finding Large Planar Subgraphs; Induced Planar Subgraphs; Planar Subgraphs; Acyclic Colorings
Acyclically Coloring GR=K_4NP-Hardness for d ≥ 4; References; List Coloring in the Absence of a Linear Forest; Introduction; A Generic Approach for Coloring H-Free Graphs; Coloring (rP1+P5)-Free Graphs; Parameterized Complexity Results; Future Work; References; Parameterized Complexity of Eulerian Deletion Problems; Introduction; Notation and Preliminaries; Polynomial-Time Solvable Cases; Eulerian Edge-Deletion Problems; FPT Algorithms; Non-existence of a Polynomial Kernel for Undirected and Directed Eulerian Edge Deletion; Node-Deletion Problems; Conclusion; References
Summary: Annotation This text constitutes the revised selected papers of the 37th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2011, held in the Czech Republic, in June 2011. The 28 revised papers presented were carefully reviewed and selected from 52 submissions.
Holdings
Item type Current library Collection Call number Status Date due Barcode Item holds
eBook eBook e-Library eBook LNCS Available
Total holds: 0

Includes bibliographical references and index.

Annotation This text constitutes the revised selected papers of the 37th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2011, held in the Czech Republic, in June 2011. The 28 revised papers presented were carefully reviewed and selected from 52 submissions.

Intro; Title page; Preface; Organization; Table of Contents; Structures and Hyperstructures in Metabolic Networks; Introduction; Structural Characterization; Dynamic Characterization; References; Important Separators and Parameterized Algorithms; Introduction; Multiway Cut; Directed Graphs; Conclusions; References; Split Clique Graph Complexity; Introduction; NP-Complete Split Clique Graph Classes; Polynomially Solvable Split Clique Graph Classes; Open Related Problems; References; On Searching for Small Kochen-Specker Vector Systems; Introduction; Kochen-Specker Vector Systems; Embeddability

Lower BoundsConclusion; References; Characterizations of Deque and Queue Graphs; Introduction; Preliminaries; Deque Graphs; Characterizing Deque Graphs; Hamiltonian Paths in Deque and Queue Graphs; Deciding If a Graph Is a Deque Graph Is NP-Complete; Queue Graphs; Conclusion; References; Graph Classes with Structured Neighborhoods and Algorithmic Applications; Introduction; Framework; Upper Bounds on Boolean-Width of Graph Classes; Vertex Partitioning Problems; Lower Bounds; Conclusion; References; Exact Algorithms for Kayles; Introduction; Preliminaries

An Upper Bound on the Number of K-setsA Bound on the Number of K-sets in Trees; The Exact Algorithm; Lower Bounds; Conclusions; References; The Cinderella Game on Holes and Anti-holes; Introduction; Definitions and First Results; The Game on General Graphs; The Game on Holes; Proof of the Upper Bound for GREEDY; Proof of the Lower Bound for GREEDY; The Game on Anti-holes; Conclusions and Conjectures; References; On the Complexity of Planar Covering of Small Graphs; Introduction; Hardness of Planar Covering of K_6; Hardness of Planar Covering of K_4, K_5, K_4+ and K_5-

Hardness of Planar Covering of the Dumbbell GraphConclusions; References; Approximability of Economic Equilibrium for Housing Markets with Duplicate Houses; Introduction; Preliminaries; Bounds for sat(M); Inapproximability; The Transformation; Inapproximability for Max-SHDTri; Inapproximability for Max-SHDTies; Conclusion and Open Problems; References; Planarization and Acyclic Colorings of Subcubic Claw-Free Graphs; Introduction; Preliminaries and Definitions; Simplifying the Graph; Finding Large Planar Subgraphs; Induced Planar Subgraphs; Planar Subgraphs; Acyclic Colorings

Acyclically Coloring GR=K_4NP-Hardness for d ≥ 4; References; List Coloring in the Absence of a Linear Forest; Introduction; A Generic Approach for Coloring H-Free Graphs; Coloring (rP1+P5)-Free Graphs; Parameterized Complexity Results; Future Work; References; Parameterized Complexity of Eulerian Deletion Problems; Introduction; Notation and Preliminaries; Polynomial-Time Solvable Cases; Eulerian Edge-Deletion Problems; FPT Algorithms; Non-existence of a Polynomial Kernel for Undirected and Directed Eulerian Edge Deletion; Node-Deletion Problems; Conclusion; References

Powered by Koha