Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers / Edition 1

Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers / Edition 1

by Juraj Hromkovic
     
 

ISBN-10: 3540241329

ISBN-13: 9783540241324

Pub. Date: 02/24/2005

Publisher: Springer Berlin Heidelberg

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

…  See more details below

Overview

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.

Product Details

ISBN-13:
9783540241324
Publisher:
Springer Berlin Heidelberg
Publication date:
02/24/2005
Series:
Lecture Notes in Computer Science Series, #3353
Edition description:
2005
Pages:
404
Product dimensions:
9.21(w) x 6.14(h) x 0.86(d)

Table of 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 Shastic 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.

Read More

Customer Reviews

Average Review:

Write a Review

and post it to your social network

     

Most Helpful Customer Reviews

See all customer reviews >