+612 9045 4394
Graph-Theoretic Concepts in Computer Science : 29th International Workshop, Wg 2003, Elspeet, the Netherlands, June 19-21, 2003, Revised Papers - Hans L. Bodlaender

Graph-Theoretic Concepts in Computer Science

29th International Workshop, Wg 2003, Elspeet, the Netherlands, June 19-21, 2003, Revised Papers

By: Hans L. Bodlaender (Editor)

Paperback Published: 29th October 2003
ISBN: 9783540204527
Number Of Pages: 392

Share This Book:


or 4 easy payments of $33.88 with Learn more
Ships in 7 to 10 business days

The 29th International Workshop on Graph-Theoretic Concepts in Computer Science(WG2003)washeldintheMennorodeconferenceCenterinElspeet, The Netherlands.TheworkshopwasorganizedbytheCenterforAlgorithmicSystems of the Institute of Information and Computing Sciences of Utrecht University. The workshop took place June 19-21, 2003. The 72 participants of WG 2003 came from universities and research institutes from 18 di?erent countries and ?ve di?erent continents. The workshop looks back at a long tradition. It was ?rst held in 1975, and has been held 20 times in Germany, twice in Austria, and once in Italy, Slo- kia, Switzerland, and the Czech Republic, and has now been held for the third time in The Netherlands. The workshop aims at uniting theory and practice by demonstrating how graph-theoretic concepts can be applied to various areas in computerscience, orbyextractingnewproblemsfromapplications.Itisdevoted to the theoretical and practical aspects of graph concepts in computer science. The goal is to present recent research results and to identify and explore - rections of future research. The talks given at the workshop showed how recent research results from algorithmic graph theory can be used in computer science and which graph-theoretic questions arise from new developments in computer science.

Blow-Ups, Win/Win's, and Crown Rules: Some New Directions in FPTp. 1
Matching Edge-Colouring, and Dimersp. 13
Minimum Flow Time Graph Orderingp. 23
Searching Is Not Jumpingp. 34
Incremental Integration Tools for Chemical Engineering: An Industrial Application of Triple Graph Grammarsp. 46
The Minimum Degree Heuristic and the Minimal Triangulation Processp. 58
Generalized Parametric Multi-terminal Flows Problemp. 71
Canonical Decomposition of Outerplanar Maps and Application to Enumeration, Coding, and Generationp. 81
The Complexity of the Matching-Cut Problem for Planar Graphs and Other Graph Classesp. 93
Tree Spanners for Bipartite Graphs and Probe Interval Graphsp. 106
A Simple Linear Time LexBFS Cograph Recognition Algorithmp. 119
Backbone Colorings for Networksp. 131
Greedy Edge-Disjoint Paths in Complete Graphsp. 143
Graph-Based Approaches to Software Watermarkingp. 156
Completely Connected Clustered Graphsp. 168
An FPT Algorithm for Set Splittingp. 180
Drawing Planar Graphs on a Curvep. 192
Tree-Partitions of k-Trees with Applications in Graph Layoutp. 205
Resource Allocation Problems in Multifiber WDM Tree Networksp. 218
An Improved Upper Bound on the Crossing Number of the Hypercubep. 230
NCE Graph Grammars and Clique-Widthp. 237
Chordal Probe Graphsp. 249
Subgraph Induced Planar Connectivity Augmentationp. 261
On the Recognition of General Partition Graphsp. 273
Short Cycles in Planar Graphsp. 284
Complexity of Hypergraph Coloring and Seidel's Switchingp. 297
Feedback Vertex Set and Longest Induced Path on AT-Free Graphsp. 309
The Complexity of Graph Contractionsp. 322
Tree Spanners, Cayley Graphs, and Diametrically Uniform Graphsp. 334
The Probabilistic Minimum Coloring Problemp. 346
Recognizing Bipolarizable and P[subscript 4]-Simplicial Graphsp. 358
Coloring Powers of Graphs of Bounded Clique-Widthp. 370
Erratum: Cycles in Generalized Networksp. 383
Author Indexp. 385
Table of Contents provided by Blackwell. All Rights Reserved.

ISBN: 9783540204527
ISBN-10: 3540204520
Series: Lecture Notes in Computer Science
Audience: General
Format: Paperback
Language: English
Number Of Pages: 392
Published: 29th October 2003
Publisher: Springer-Verlag Berlin and Heidelberg Gmbh & Co. Kg
Country of Publication: DE
Dimensions (cm): 23.39 x 15.6  x 2.11
Weight (kg): 0.56