计算机科学中的图论概念： WG 2006/会议录 Graph-theoretic concepts in computer science

This book constitutes the thoroughly refereed post-proceedings of the 32nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2006, held in Bergen, Norway in June 2006.
The 30 revised full papers presented together with 1 invited paper were carefully selected from 91 submissions. The papers address all aspects of graph-theoretic concepts in computer science such as structural graph theory, sequential, parallel, and distributed graph and network algorithms and their complexity, graph grammars and graph rewriting systems, graph-based modeling, graph-drawing and layout, diagram methods, and graph-theoretical applications in various fields.

The LNCS series reports state-of-the-art results in computer science research,development,and education,at a high level and in both printed and electronic form.Enjoying tight cooperation with the R&D community,with numerous individuals,as well as with prestigious organizations and societies,LNCS has grown into the most comprehensive computer science resarch forum available.
The scope of LNCS,including its subseries LNAI,spans the whole range of computer science and information technology including interdisciplinary topics in a variety of application fields.The type of material publised traditionally includes.
-proceedings(published in time for the respective conference)
-post-proceedings(consisting of thoroughly revised final full papers)
-research monographs(which may be basde on outstanding PhD work,research projects,technical reports,etc.).

Treewidth: Characterizations, Applications, and Computations
Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy
Generalised Dualities and Finite Maximal Antichains
Chordal Deletion Is Fixed-Parameter Tractable
A Fixed-Parameter Algorithm for the Minimum Weight Triangulation Problem Based on Small Graph Separators
Divide-and-Color
Listing Chordal Graphs and Interval Graphs
A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set in Graphs
Improved Edge-Coloring with Three Colors
Vertex Coloring of Comparability+ke and -ke Graphs
Convex Drawings of Graphs with Non-convex Boundary
How to Sell a Graph: Guidelines for Graph Retailers
Strip Graphs: Recognition and Scheduling
Approximating the Traffic Grooming Problem in Tree and Star Networks
Bounded Arboricity to Determine the Local Structure of Sparse Graphs
An Implicit Representation of Chordal Comparabilty Graphs in Linear-Time
Partitioned Probe Comparability Graphs
Computing Graph Polynomials on Graphs of Bounded Clique-Width
Generation of Graphs with Bounded Branchwidth
Minimal Proper Interval Completions
Monotony Properties of Connected Visible Graph Searching
Finding Intersection Models of Weakly Chordal Graphs
A Fully Dynamic Algorithm for the Recognition of P4-Sparse Graphs
Clique Graph Recognition Is NP-Complete
Homogeneity vs. Adjacency: Generalising Some Graph Decomposition Algorithms
Certifying Algorithms for Recognizing Proper Circular-Arc Graphs and Unit Circular-Arc Graphs
……
Author Index