Coverart for item
The Resource 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.)

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.)

Label
Graph-theoretic concepts in computer science : 37th International Workshop, WG 2011, Teplá Monastery, Czech Republic, June 21-24, 2011 : revised papers
Title
Graph-theoretic concepts in computer science
Title remainder
37th International Workshop, WG 2011, Teplá Monastery, Czech Republic, June 21-24, 2011 : revised papers
Statement of responsibility
Petr Kolman, Jan Kratochvíl (eds.)
Creator
Contributor
Subject
Genre
Language
eng
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
Member of
Cataloging source
GW5XE
Dewey number
511/.5
Illustrations
illustrations
Index
index present
LC call number
QA166
LC item number
.C664 2011
Literary form
non fiction
http://bibfra.me/vocab/lite/meetingDate
2011
http://bibfra.me/vocab/lite/meetingName
International Workshop WG
Nature of contents
  • dictionaries
  • bibliography
http://library.link/vocab/relatedWorkOrContributorName
  • Kolman, Petr
  • Kratochvíl, Jan
Series statement
  • Lecture notes in computer science,
  • Lecture notes in computer science. Advanced research in computing and software science
Series volume
6986
http://library.link/vocab/subjectName
  • Graph theory
  • Computer science
  • Graph theory
  • Informatique
  • Computer science
  • Graph theory
  • Graph theory
  • Engineering & Applied Sciences
  • Computer Science
Label
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.)
Instantiates
Publication
Antecedent source
unknown
Bibliography note
Includes bibliographical references and index
Carrier category
online resource
Carrier category code
  • cr
Carrier MARC source
rdacarrier
Color
multicolored
Content category
text
Content type code
  • txt
Content type MARC source
rdacontent
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 {u2265} 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
Control code
768244618
Dimensions
unknown
Extent
1 online resource (xi, 344 pages)
File format
unknown
Form of item
online
Isbn
9783642258701
Level of compression
unknown
Media category
computer
Media MARC source
rdamedia
Media type code
  • c
Other control number
10.1007/978-3-642-25870-1
Other physical details
illustrations (some color).
Quality assurance targets
not applicable
Reformatting quality
unknown
Sound
unknown sound
Specific material designation
remote
System control number
(OCoLC)768244618
Label
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.)
Publication
Antecedent source
unknown
Bibliography note
Includes bibliographical references and index
Carrier category
online resource
Carrier category code
  • cr
Carrier MARC source
rdacarrier
Color
multicolored
Content category
text
Content type code
  • txt
Content type MARC source
rdacontent
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 {u2265} 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
Control code
768244618
Dimensions
unknown
Extent
1 online resource (xi, 344 pages)
File format
unknown
Form of item
online
Isbn
9783642258701
Level of compression
unknown
Media category
computer
Media MARC source
rdamedia
Media type code
  • c
Other control number
10.1007/978-3-642-25870-1
Other physical details
illustrations (some color).
Quality assurance targets
not applicable
Reformatting quality
unknown
Sound
unknown sound
Specific material designation
remote
System control number
(OCoLC)768244618

Library Locations

    • Ellis LibraryBorrow it
      1020 Lowry Street, Columbia, MO, 65201, US
      38.944491 -92.326012
    • Engineering Library & Technology CommonsBorrow it
      W2001 Lafferre Hall, Columbia, MO, 65211, US
      38.946102 -92.330125
Processing Feedback ...