## Graph-Theoretic Concepts in Computer Science: 27th International Workshop, WG 2001 Boltenhagen, Germany, June 14-16, 2001 Proceedings, Volume 27This 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 |

328 | |

### Other editions - View all

Graph-Theoretic Concepts in Computer Science: 27th International ..., Volume 27 Andreas Brandstädt No preview available - 2001 |

Graph-Theoretic Concepts in Computer Science Andreas Brandstädt,Van Bang Le No preview available - 2014 |

### Common terms and phrases

2-level cactus adjacent anticritical approximation algorithms assigned assume Berlin Heidelberg 2001 bipartite graph Brandstädt and V.B. chordal graphs chromatic number clique transversal set clique-width cographs complete bipartite graphs Computer Science connected components consider construction contains corresponding cycle deﬁned deﬁnition denote DH(k disjoint distance distance-hereditary distance-hereditary graphs edge coloring edge order exists follow the sp-rules full components given graph classes graph G Hence hotlinks induced subgraph input integer interval graphs k-subcoloring k-tree label least Lemma length Let G linear lower bound matching-cut maximum clique transversal maximum degree minimal minimum vertex cover multi set neighbor NLC-width nodes NP-complete NP-hard obtained optimal outerplanar graphs pair partition path decomposition pathwidth perfect graphs perfect matching planar graph polynomial Proof prove result sequence shortest path stable cutset star coloring strong asteroid subcoloring subset subtrees Theorem treewidth triangulated U-parts union step V.B. Le Eds vertex set width