Logo - springer
Slogan - springer

Computer Science - Theoretical Computer Science | Graph-Theoretic Concepts in Computer Science - 31st International Workshop, WG 2005, Metz, France,

Graph-Theoretic Concepts in Computer Science

31st International Workshop, WG 2005, Metz, France, June 23-25, 2005, Revised Selected Papers

Kratsch, Dieter (Ed.)

2005, XIV, 470 p. Also available online.

Available Formats:

Springer eBooks may be purchased by end-customers only and are sold without copy protection (DRM free). Instead, all eBooks include personalized watermarks. This means you can read the Springer eBooks across numerous devices such as Laptops, eReaders, and tablets.

You can pay for Springer eBooks with Visa, Mastercard, American Express or Paypal.

After the purchase you can directly download the eBook file or read it online in our Springer eBook Reader. Furthermore your eBook will be stored in your MySpringer account. So you can always re-download your eBooks.


(net) price for USA

ISBN 978-3-540-31468-4

digitally watermarked, no DRM

Included Format: PDF

download immediately after purchase

learn more about Springer eBooks

add to marked items


Softcover (also known as softback) version.

You can pay for Springer Books with Visa, Mastercard, American Express or Paypal.

Standard shipping is free of charge for individual customers.


(net) price for USA

ISBN 978-3-540-31000-6

free shipping for individuals worldwide

usually dispatched within 3 to 5 business days

add to marked items

  • About this book

The 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2005) was held on the campus “Ile du Saulcy” of the Univ- sity Paul Verlaine-Metz in France. The workshop was organized by the La- ratoire d’Informatique Th´ eorique et Appliqu´ ee (LITA) and it took place June 23 – 25 2005. The 94 participants of WG 2005 came from universities and - search institutes of 18 di?erent countries. The WG 2005 workshop continues the series of 30 previous WG workshops. Since 1975,WG has taken place 20 times in Germany, four times in The Neth- lands,twotimesinAustriaaswellasonceinItaly,inSlovakia,inSwitzerlandand inCzechRepublic, andhas nowbeen heldfor the ?rsttime inFrance.The wo- shop aims at uniting theory and practice by demonstrating how graph-theoretic concepts can be applied to various areas in computer science, or by extracting new problems from applications. The goal is to present recent research results and to identify and explore directions of future research. The talks were given in the “Petit Th´ eatre”. They showed how recent research results from algori- mic graph theory can be used in computer science and which graph-theoretic questions arise from new developments in computer science. There were two fascinating invited lectures by Georg Gottlob (Vienna, Austria) and Gregory Kucherov (Nancy, France).

Content Level » Research

Keywords » Algorithms - Graph - algorithm - algorithmic geometry - algorithmic graph theory - approximation - combinatorial optimization - complexity theory - computational discrete mathematics - computer - computer science - graph algorithms - graph coloring - graph computations - graph decomposition

Related subjects » Theoretical Computer Science

Table of contents 

Invited Lectures.- Hypertree Decompositions: Structure, Algorithms, and Applications.- Combinatorial Search on Graphs Motivated by Bioinformatics Applications: A Brief Survey.- Regular Papers.- Domination Search on Graphs with Low Dominating-Target-Number.- Fully Dynamic Algorithm for Recognition and Modular Decomposition of Permutation Graphs.- Approximating Rank-Width and Clique-Width Quickly.- Computing the Tutte Polynomial on Graphs of Bounded Clique-Width.- Minimizing NLC-Width is NP-Complete.- Channel Assignment and Improper Choosability of Graphs.- Computing Treewidth and Minimum Fill-In for Permutation Graphs in Linear Time.- Roman Domination over Some Graph Classes.- Algorithms for Comparability of Matrices in Partial Orders Imposed by Graph Homomorphisms.- Network Discovery and Verification.- Complete Graph Drawings Up to Triangle Mutations.- Collective Tree 1-Spanners for Interval Graphs.- On Stable Cutsets in Claw-Free Graphs and Planar Graphs.- Induced Subgraphs of Bounded Degree and Bounded Treewidth.- Optimal Broadcast Domination of Arbitrary Graphs in Polynomial Time.- Ultimate Generalizations of LexBFS and LEX M.- Adding an Edge in a Cograph.- The Computational Complexity of Delay Management.- Acyclic Choosability of Graphs with Small Maximum Degree.- Generating Colored Trees.- Optimal Hypergraph Tree-Realization.- Fixed-Parameter Algorithms for Protein Similarity Search Under mRNA Structure Constraints.- On the Fixed-Parameter Enumerability of Cluster Editing.- Locally Consistent Constraint Satisfaction Problems with Binary Constraints.- On Randomized Broadcasting in Star Graphs.- Finding Disjoint Paths on Directed Acyclic Graphs.- Approximation Algorithms for the Bi-criteria Weighted max-cut Problem.- Approximation Algorithms for the Weighted Independent Set Problem.- Approximation Algorithms for Unit Disk Graphs.- Computation of Chromatic Polynomials Using Triangulations and Clique Trees.- Computing Branchwidth Via Efficient Triangulations and Blocks.- Algorithms Based on the Treewidth of Sparse Graphs.- Extending the Tractability Border for Closest Leaf Powers.- Bounding the Misclassification Error in Spectral Partitioning in the Planted Partition Model.- Algebraic Operations on PQ Trees and Modular Decomposition Trees.- Linear-Time Counting Algorithms for Independent Sets in Chordal Graphs.- Faster Dynamic Algorithms for Chordal Graphs, and an Application to Phylogeny.- Recognizing HHDS-Free Graphs.

Popular Content within this publication 



Read this Book on Springerlink

Services for this book

New Book Alert

Get alerted on new Springer publications in the subject area of Theory of Computation.