Graph-Theoretic Concepts in Computer Science计算机科学中的图论概念

书籍目录

Invited Papers  Lexicographic Breadth First Search - A Survey  Wireless Networking: Graph Theory UnpluggedGraph 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 DecompositionGraph 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 CLOptimization and Approximation Algorithms  The Computational Complexity of the Mininmum 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(n2) Steps  Counting, Combinatorics, and Optimization  Planar Graphs, via Well-Orderly Maps and Trees ……Applications (Biology,Graph Drawing)Graph Classes and NP Hardness Author Index

作者简介

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.

 Graph-Theoretic Concepts in Computer Science计算机科学中的图论概念下载