# 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: (37th : International Workshop WG (37th : 2011 : Teplá, Czech Republic)

##### Contributor(s): Kolman, Petr | Kratochvíl, Jan

Material type: TextSeries: SerienbezeichnungLecture notes in computer science: 6986.; Lecture notes in computer science: Publisher: Heidelberg ; New York : Springer-Verlag, ©2011Description: 1 online resource (xi, 344 pages) : illustrations (some color)Content type: text Media type: computer Carrier type: online resourceISBN: 9783642258701; 3642258700; 3642258697; 9783642258695Subject(s): Graph theory -- Data processing -- Congresses | Computer science -- Congresses | Graph theory -- Congresses | Informatique | Computer science | Graph theory | Graph theory -- Data processing | Engineering & Applied Sciences | Computer Science | Computer science | Computer Communication Networks | Data structures (Computer science) | Computer software | Computational complexity | Algorithms | Geometry | Discrete Mathematics in Computer Science | Algorithm Analysis and Problem Complexity | Data StructuresGenre/Form: Electronic books. | Conference papers and proceedings. Additional physical formats: Printed edition:: No titleDDC classification: 511/.5 LOC classification: QA166 | .C664 2011Online resources: Click here to access onlineItem type | Current location | Collection | Call number | Status | Date due | Barcode | Item holds |
---|---|---|---|---|---|---|---|

eBook |
e-Library
Electronic Book@IST |
EBook | Available |

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

There are no comments for this item.