Description |
1 online resource (xi, 404 pages) : illustrations |
Series |
Lecture notes in computer science, 0302-9743 ; 3353 |
|
Lecture notes in computer science ; 3353.
|
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 |
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 |
Analysis |
computerwetenschappen |
|
computer sciences |
|
Information and Communication Technology (General) |
|
Informatie- en communicatietechnologie (algemeen) |
Bibliography |
Includes bibliographical references and index |
Notes |
Print version record |
Subject |
Computer science -- Congresses
|
|
Graph theory -- Congresses
|
|
Informatique.
|
|
Computer science
|
|
Graph theory
|
|
Informatique.
|
|
Théorie des graphes.
|
Genre/Form |
proceedings (reports)
|
|
Conference papers and proceedings
|
|
Conference papers and proceedings.
|
|
Actes de congrès.
|
Form |
Electronic book
|
Author |
Hromkovič, Juraj, 1958-
|
|
Nagl, Manfred, 1944-
|
|
Westfechtel, Bernhard, 1958-
|
ISBN |
9783540305590 |
|
3540305599 |
|
3540241329 |
|
9783540241324 |
|