Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers

Pirmais vāks
Springer Science & Business Media, 2004. gada 21. dec. - 404 lappuses
During its 30-year existence, the International Workshop on Graph-Theoretic Concepts in Computer Science has become a distinguished and high-quality computer science event. The workshop aims at uniting theory and practice by demonstrating how graph-theoretic concepts can successfully be applied to v- ious areas of computer science and by exposing new theories emerging from applications. In this way, WG provides a common ground for the exchange of information among people dealing with several graph problems and working in various disciplines. Thereby, the workshop contributes to forming an interdis- plinary research community. The original idea of the Workshop on Graph-Theoretic Concepts in C- puter Science was ingenuity in all theoretical aspects and applications of graph concepts, wherever applied. Within the last ten years, the development has strengthened in particular the topic of structural graph properties in relation to computational complexity. This workshop has become pivotal for the c- munity interested in these areas.An aimspeci?c to the 30thWG was to support the central role of WG in both of the prementioned areas on the one hand and on the other hand to promote its originally broader scope. The 30th WG was held at the Physikzentrum Bad Honnef, which serves as the main meeting point of the German Physical Society. It o?ers a secluded setting for research conferences, seminars, and workshops, and has proved to be especiallystimulatingforfruitful discussions.Talksweregiveninthenewlecture hall with a modern double rear projection, interactive electronic board, and full video conferencing equipment.

No grāmatas satura

Saturs

Invited Papers
1
Graph Theory Unplugged
20
Trees
33
Collective Tree Spanners and Routing in ATfree Related Graphs
68
Recognition and Decomposition
81
Recognizing HHDfree and WelshPowell Opposition Graphs
105
Coloring a Graph Using Split Decomposition
129
Various Problems
142
Parameterized Complexity and Exponential Algorithms
235
Linear Kernels in Linear Time or How to Save k Colors in On2 Steps
257
Counting Combinatorics and Optimization
270
Efficient Computation of the Lovasz Theta Function
285
Applications Biology Graph Drawing
308
Crossing Reduction in Circular Layouts
332
EdgeConnectivity Augmentation and Network Matrices
355
Complexity and Approximability Results
377

Minimal de Bruijn Sequence in a Language with Forbidden Substrings
168
Optimization and Approximation Algorithms
189
A Robust PTAS for Maximum Weight Independent Sets
214

Citi izdevumi - Skatīt visu

Bieži izmantoti vārdi un frāzes

Bibliogrāfiskā informācija