Borrow it
Coverart for item
The Resource Graph-theoretic concepts in computer science : 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004 : revised papers, Juraj Hromkovič, Manfred Nagl, Bernhard Westfechtel (eds.)

Graph-theoretic concepts in computer science : 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004 : revised papers, Juraj Hromkovič, Manfred Nagl, Bernhard Westfechtel (eds.)

Creator
Contributor
Summary
This book constitutes the thoroughly refereed post-proceedings of the 30th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2004, held in Bad Honnef, Germany in June 2004. The 31 revised full papers presented together with 2 invited papers were carefully selected from 66 submissions during two rounds of reviewing and improvement. The papers are organized in topical sections on graph algorithms: trees; graph algorithms: recognition and decomposition; graph algorithms: various problems; optimization and approximation algorithms; parameterized complexity and exponential algorithms; counting, combinatorics, and optimization; applications in bioinformatics and graph drawing; and graph classes and NP-hard problems
Language
eng
Work
Publication
Extent
1 online resource (xi, 404 pages)
Contents
  • Invited Papers
  • Lexicographic Breadth First Search
  • A Survey
  • Wireless Networking: Graph Theory Unplugged
  • Graph Algorithms: Trees
  • Constant Time Generation of Trees with Specified Diameter
  • Treelike Comparability Graphs: Characterization, Recognition, and Applications
  • Elegant Distance Constrained Labelings of Trees
  • Collective Tree Spanners and Routing in AT-free Related Graphs
  • Graph Algorithms: Recognition and Decomposition
  • On the Maximum Cardinality Search Lower Bound for Treewidth
  • Fully-Dynamic Recognition Algorithm and Certificate for Directed Cographs
  • Recognizing HHD-free and Welsh-Powell Opposition Graphs
  • Bimodular Decomposition of Bipartite Graphs
  • Coloring a Graph Using Split Decomposition
  • Graph Algorithms: Various Problems
  • Decremental Clique Problem
  • A Symbolic Approach to the All-Pairs Shortest-Paths Problem
  • Minimal de Bruijn Sequence in a Language with Forbidden Substrings
  • A Graph-Theoretic Generalization of the Least Common Subsumer and the Most Specific Concept in the Description Logic
  • Optimization and Approximation Algorithms
  • The Computational Complexity of the Minimum Weight Processor Assignment Problem
  • A Stochastic Location Problem with Applications to Tele-diagnostic
  • A Robust PTAS for Maximum Weight Independent Sets in Unit Disk Graphs
  • Tolerance Based Algorithms for the ATSP
  • Parameterized Complexity and Exponential Algorithms
  • Finding k Disjoint Triangles in an Arbitrary Graph
  • Exact (Exponential) Algorithms for the Dominating Set Problem
  • Linear Kernels in Linear Time, or How to Save k Colors in O(n 2) Steps
  • Counting, Combinatorics, and Optimization
  • Planar Graphs, via Well-Orderly Maps and Trees
  • Efficient Computation of the Lovász Theta Function for a Class of Circulant Graphs
  • Unhooking Circulant Graphs: A Combinatorial Method for Counting Spanning Trees and Other Parameters
  • Applications (Biology, Graph Drawing)
  • Computing Bounded-Degree Phylogenetic Roots of Disconnected Graphs
  • Octagonal Drawings of Plane Graphs with Prescribed Face Areas
  • Crossing Reduction in Circular Layouts
  • Graph Classes and NP Hardness
  • Characterization and Recognition of Generalized Clique-Helly Graphs
  • Edge-Connectivity Augmentation and Network Matrices
  • Partitioning a Weighted Graph to Connected Subgraphs of Almost Uniform Size
  • The Hypocoloring Problem: Complexity and Approximability Results when the Chromatic Number Is Small
  • Core Stability of Minimum Coloring Games
Isbn
9783540305590
Instance
Label
Graph-theoretic concepts in computer science : 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004 : revised papers
Title
Graph-theoretic concepts in computer science
Title remainder
30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004 : revised papers
Statement of responsibility
Juraj Hromkovič, Manfred Nagl, Bernhard Westfechtel (eds.)
Title variation
WG 2004
Creator
Contributor
Subject
Genre
Language
eng
Summary
This book constitutes the thoroughly refereed post-proceedings of the 30th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2004, held in Bad Honnef, Germany in June 2004. The 31 revised full papers presented together with 2 invited papers were carefully selected from 66 submissions during two rounds of reviewing and improvement. The papers are organized in topical sections on graph algorithms: trees; graph algorithms: recognition and decomposition; graph algorithms: various problems; optimization and approximation algorithms; parameterized complexity and exponential algorithms; counting, combinatorics, and optimization; applications in bioinformatics and graph drawing; and graph classes and NP-hard problems
Member of
Cataloging source
GW5XE
Dewey number
511.5
Illustrations
illustrations
Index
index present
LC call number
QA75.5
LC item number
.I649 2004
Literary form
non fiction
http://bibfra.me/vocab/lite/meetingDate
2004
http://bibfra.me/vocab/lite/meetingName
International Workshop WG
Nature of contents
  • dictionaries
  • bibliography
http://library.link/vocab/relatedWorkOrContributorDate
  • 1958-
  • 1944-
  • 1958-
http://library.link/vocab/relatedWorkOrContributorName
  • Hromkovič, Juraj
  • Nagl, Manfred
  • Westfechtel, Bernhard
Series statement
Lecture notes in computer science,
Series volume
3353
http://library.link/vocab/subjectName
  • Computer science
  • Graph theory
  • Informatique
  • Théorie des graphes
  • Informatique
  • Computer science
  • Graph theory
  • Informatique
  • Théorie des graphes
Label
Graph-theoretic concepts in computer science : 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004 : revised papers, Juraj Hromkovič, Manfred Nagl, Bernhard Westfechtel (eds.)
Instantiates
Publication
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
Invited Papers -- Lexicographic Breadth First Search -- A Survey -- Wireless Networking: Graph Theory Unplugged -- Graph Algorithms: Trees -- Constant Time Generation of Trees with Specified Diameter -- Treelike Comparability Graphs: Characterization, Recognition, and Applications -- Elegant Distance Constrained Labelings of Trees -- Collective Tree Spanners and Routing in AT-free Related Graphs -- Graph Algorithms: Recognition and Decomposition -- On the Maximum Cardinality Search Lower Bound for Treewidth -- Fully-Dynamic Recognition Algorithm and Certificate for Directed Cographs -- Recognizing HHD-free and Welsh-Powell Opposition Graphs -- Bimodular Decomposition of Bipartite Graphs -- Coloring a Graph Using Split Decomposition -- Graph Algorithms: Various Problems -- Decremental Clique Problem -- A Symbolic Approach to the All-Pairs Shortest-Paths Problem -- Minimal de Bruijn Sequence in a Language with Forbidden Substrings -- A Graph-Theoretic Generalization of the Least Common Subsumer and the Most Specific Concept in the Description Logic -- Optimization and Approximation Algorithms -- The Computational Complexity of the Minimum Weight Processor Assignment Problem -- A Stochastic Location Problem with Applications to Tele-diagnostic -- A Robust PTAS for Maximum Weight Independent Sets in Unit Disk Graphs -- Tolerance Based Algorithms for the ATSP -- Parameterized Complexity and Exponential Algorithms -- Finding k Disjoint Triangles in an Arbitrary Graph -- Exact (Exponential) Algorithms for the Dominating Set Problem -- Linear Kernels in Linear Time, or How to Save k Colors in O(n 2) Steps -- Counting, Combinatorics, and Optimization -- Planar Graphs, via Well-Orderly Maps and Trees -- Efficient Computation of the Lovász Theta Function for a Class of Circulant Graphs -- Unhooking Circulant Graphs: A Combinatorial Method for Counting Spanning Trees and Other Parameters -- Applications (Biology, Graph Drawing) -- Computing Bounded-Degree Phylogenetic Roots of Disconnected Graphs -- Octagonal Drawings of Plane Graphs with Prescribed Face Areas -- Crossing Reduction in Circular Layouts -- Graph Classes and NP Hardness -- Characterization and Recognition of Generalized Clique-Helly Graphs -- Edge-Connectivity Augmentation and Network Matrices -- Partitioning a Weighted Graph to Connected Subgraphs of Almost Uniform Size -- The Hypocoloring Problem: Complexity and Approximability Results when the Chromatic Number Is Small -- Core Stability of Minimum Coloring Games
Control code
324999336
Dimensions
unknown
Extent
1 online resource (xi, 404 pages)
Form of item
online
Isbn
9783540305590
Media category
computer
Media MARC source
rdamedia
Media type code
  • c
Other control number
  • 9783540241324
  • 10.1007/b104584
Other physical details
illustrations.
http://library.link/vocab/ext/overdrive/overdriveId
978-3-540-24132-4
Specific material designation
remote
System control number
(OCoLC)324999336
Label
Graph-theoretic concepts in computer science : 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004 : revised papers, Juraj Hromkovič, Manfred Nagl, Bernhard Westfechtel (eds.)
Publication
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
Invited Papers -- Lexicographic Breadth First Search -- A Survey -- Wireless Networking: Graph Theory Unplugged -- Graph Algorithms: Trees -- Constant Time Generation of Trees with Specified Diameter -- Treelike Comparability Graphs: Characterization, Recognition, and Applications -- Elegant Distance Constrained Labelings of Trees -- Collective Tree Spanners and Routing in AT-free Related Graphs -- Graph Algorithms: Recognition and Decomposition -- On the Maximum Cardinality Search Lower Bound for Treewidth -- Fully-Dynamic Recognition Algorithm and Certificate for Directed Cographs -- Recognizing HHD-free and Welsh-Powell Opposition Graphs -- Bimodular Decomposition of Bipartite Graphs -- Coloring a Graph Using Split Decomposition -- Graph Algorithms: Various Problems -- Decremental Clique Problem -- A Symbolic Approach to the All-Pairs Shortest-Paths Problem -- Minimal de Bruijn Sequence in a Language with Forbidden Substrings -- A Graph-Theoretic Generalization of the Least Common Subsumer and the Most Specific Concept in the Description Logic -- Optimization and Approximation Algorithms -- The Computational Complexity of the Minimum Weight Processor Assignment Problem -- A Stochastic Location Problem with Applications to Tele-diagnostic -- A Robust PTAS for Maximum Weight Independent Sets in Unit Disk Graphs -- Tolerance Based Algorithms for the ATSP -- Parameterized Complexity and Exponential Algorithms -- Finding k Disjoint Triangles in an Arbitrary Graph -- Exact (Exponential) Algorithms for the Dominating Set Problem -- Linear Kernels in Linear Time, or How to Save k Colors in O(n 2) Steps -- Counting, Combinatorics, and Optimization -- Planar Graphs, via Well-Orderly Maps and Trees -- Efficient Computation of the Lovász Theta Function for a Class of Circulant Graphs -- Unhooking Circulant Graphs: A Combinatorial Method for Counting Spanning Trees and Other Parameters -- Applications (Biology, Graph Drawing) -- Computing Bounded-Degree Phylogenetic Roots of Disconnected Graphs -- Octagonal Drawings of Plane Graphs with Prescribed Face Areas -- Crossing Reduction in Circular Layouts -- Graph Classes and NP Hardness -- Characterization and Recognition of Generalized Clique-Helly Graphs -- Edge-Connectivity Augmentation and Network Matrices -- Partitioning a Weighted Graph to Connected Subgraphs of Almost Uniform Size -- The Hypocoloring Problem: Complexity and Approximability Results when the Chromatic Number Is Small -- Core Stability of Minimum Coloring Games
Control code
324999336
Dimensions
unknown
Extent
1 online resource (xi, 404 pages)
Form of item
online
Isbn
9783540305590
Media category
computer
Media MARC source
rdamedia
Media type code
  • c
Other control number
  • 9783540241324
  • 10.1007/b104584
Other physical details
illustrations.
http://library.link/vocab/ext/overdrive/overdriveId
978-3-540-24132-4
Specific material designation
remote
System control number
(OCoLC)324999336

Subject

Genre

Member of

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

Library Links

Structured data from the Bibframe namespace is licensed under the Creative Commons Attribution 4.0 International License by University of Missouri Libraries. Additional terms may apply to data associated with third party namespaces.
Processing Feedback ...