Graph-Theoretic Concepts in Computer Science: 27th International Workshop, WG 2001 Boltenhagen, Germany, June 14-16, 2001 Proceedings, Volume 27

Front Cover
Springer Science & Business Media, Sep 26, 2001 - Computers - 327 pages
This book constitutes the thoroughly refereed post-workshop proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2001, held in Boltenhagen, Germany, in June 2001.
The 27 revised full papers presented together with two invited contributions were carefully reviewed and selected from numerous submissions. The papers provide a wealth of new results for various classes of graphs, graph computations, graph algorithms and graph-theoretical applications in various fields.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Median Hulls as Steiner Hulls in Rectilinear and Molecular Sequence Spaces
1
Data Management in Networks
8
EdgeIsoperimetric Problems for Cartesian Powers of Regular Graphs
9
Approximate Constrained Bipartite Edge Coloring
21
Maximum Clique Transversals
32
On the TreeDegree of Graphs
44
Improved Algorithms
55
k+DistanceHereditary Graphs
66
On the Monotonicity of Games Generated by Symmetric Submodular Functions
177
Multiple Hotlink Assignment
189
Small kDominating Sets in Planar Graphs with Applications
201
Lower Bounds for Approximation Algorithms for the Steiner Tree Problem
217
log nApproximative NLCkDecomposition in On2k+1 Time
229
On Subfamilies of ATFree Graphs
241
Complexity of Coloring Graphs without Forbidden Induced Subgraphs
254
On Stable Cutsets in Line Graphs
263

On the Relationship between CliqueWidth and Treewidth
78
Planarity of the 2Level Cactus Model
91
A Unified Approach
103
How to Solve NPhard Graph Problems on CliqueWidth Bounded Graphs in Polynomial Time
117
g fFactorizations Orthogonal to k Subgraphs
129
On Star Coloring of Graphs
140
Complexity and Algorithms
154
Approximation of Pathwidth of Outerplanar Graphs
166
On Strong MengerConnectivity of Star Graphs
272
The Complexity of the MatchingCut Problem
284
De Bruijn Graphs and DNA Graphs
296
A Generic Greedy Algorithm PartiallyOrdered Graphs and NPCompleteness
306
Critical and Anticritical Edges in Perfect Graphs
317
Author Index
328
Copyright

Other editions - View all

Common terms and phrases