Graph-Theoretic Concepts in Computer Science 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers
During its 30-year existence, the International Workshop on Graph-Theoretic Concepts in Computer Science has become a distinguished and high-quality computer science event. The workshop aims at uniting theory and practice by demonstrating how graph-theoretic concepts can successfully be applied to v...
| Other Authors: | , , |
|---|---|
| Format: | eBook |
| Language: | English |
| Published: |
Berlin, Heidelberg
Springer Berlin Heidelberg
2005, 2005
|
| Edition: | 1st ed. 2005 |
| Series: | Lecture Notes in Computer Science
|
| Subjects: | |
| Online Access: | |
| Collection: | Springer eBooks 2005- - Collection details see MPG.ReNa |
Table of Contents:
- 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
- UnhookingCirculant 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
- 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