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: TextTextSeries: 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 online
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.
Tags from this library: No tags from this library for this title. Log in to add tags.
    Average rating: 0.0 (0 votes)
Item type Current location Collection Call number Status Date due Barcode Item holds
eBook eBook e-Library

Electronic Book@IST

EBook 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

There are no comments for this item.

to post a comment.

Powered by Koha