Graph-Theoretic Concepts in Computer Science

29th International Workshop, WG 2003, Elspeet, The Netherlands, June 19-21, 2003, Revised Papers

Buch | Softcover

XII, 392 Seiten

2003 | 2003
Springer Berlin (Verlag)
978-3-540-20452-7 (ISBN)

Artikel merken

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.

Invited Lecture.- Blow-Ups, Win/Win's, and Crown Rules: Some New Directions in FPT.- Matching, Edge-Colouring, and Dimers.- Regular Papers.- Minimum Flow Time Graph Ordering.- Searching Is Not Jumping.- Incremental Integration Tools for Chemical Engineering: An Industrial Application of Triple Graph Grammars.- The Minimum Degree Heuristic and the Minimal Triangulation Process.- Generalized Parametric Multi-terminal Flows Problem.- Canonical Decomposition of Outerplanar Maps and Application to Enumeration, Coding, and Generation.- The Complexity of the Matching-Cut Problem for Planar Graphs and Other Graph Classes.- Tree Spanners for Bipartite Graphs and Probe Interval Graphs.- A Simple Linear Time LexBFS Cograph Recognition Algorithm.- Backbone Colorings for Networks.- Greedy Edge-Disjoint Paths in Complete Graphs.- Graph-Based Approaches to Software Watermarking.- Completely Connected Clustered Graphs.- An FPT Algorithm for Set Splitting.- Drawing Planar Graphs on a Curve.- Tree-Partitions of k-Trees with Applications in Graph Layout.- Resource Allocation Problems in Multifiber WDM Tree Networks.- An Improved Upper Bound on the Crossing Number of the Hypercube.- NCE Graph Grammars and Clique-Width.- Chordal Probe Graphs.- Subgraph Induced Planar Connectivity Augmentation.- On the Recognition of General Partition Graphs.- Short Cycles in Planar Graphs.- Complexity of Hypergraph Coloring and Seidel's Switching.- Feedback Vertex Set and Longest Induced Path on AT-Free Graphs.- The Complexity of Graph Contractions.- Tree Spanners, Cayley Graphs, and Diametrically Uniform Graphs.- The Probabilistic Minimum Coloring Problem.- Recognizing Bipolarizable and P 4-Simplicial Graphs.- Coloring Powers of Graphs of Bounded Clique-Width.- Erratum.- Erratum: Cycles in GeneralizedNetworks.

Erscheint lt. Verlag	29.10.2003
Reihe/Serie	Lecture Notes in Computer Science
Zusatzinfo	XII, 392 p.
Verlagsort	Berlin
Sprache	englisch
Maße	155 x 235 mm
Gewicht	567 g
Themenwelt	Informatik ► Theorie / Studium ► Algorithmen
Themenwelt	Mathematik / Informatik ► Mathematik
Schlagworte	Algorithm analysis and problem complexity • Algorithmic Graph Theory • algorithms • Approximation • Computational Discrete Mathematics • Computational Geometry • Computer • Computer Science • data structures • geometric algorithms • Graph • Graph Algorithms • graph coloring • Graph Computations • graph contractions • Graph Drawing • Graph Grammars • network algorithms
ISBN-10	3-540-20452-0 / 3540204520
ISBN-13	978-3-540-20452-7 / 9783540204527
Zustand	Neuware