Logo - springer
Slogan - springer

Computer Science - Theoretical Computer Science | Graph-Theoretic Concepts in Computer Science - 35th International Workshop, WG 2009, Montpellier,

Graph-Theoretic Concepts in Computer Science

35th International Workshop, WG 2009, Montpellier, France, June 24-26, 2009, Revised Papers

Paul, Christophe, Habib, Michel (Eds.)

2010, XIII, 353 p.

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-642-11409-0

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-642-11408-3

free shipping for individuals worldwide

online orders shipping within 2-3 days.

add to marked items

This book constitutes the thoroughly refereed post-conference proceedings of the 35th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2009, held in Montpellier, France, in June 2009.

The 28 revised full papers presented together with two invited papers were carefully reviewed and selected from 69 submissions. The papers feature original results on all aspects of graph-theoretic concepts in Computer Science, e.g. 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 support of these concepts by suitable implementations.

Content Level » Research

Keywords » Graph - algorithms - chordal graphs - claw-free graphs - complexity - computational geometry - edge colorings - graph algorithms - graph partitioning - k-disjoint graph problem - minimum spanning trees - modeling - planar graphs - switch graphs

Related subjects » Computational Science & Engineering - Geometry & Topology - Theoretical Computer Science

Table of contents 

Graph-Theoretic Solutions to Computational Geometry Problems.- Algorithms for Classes of Graphs with Bounded Expansion.- A Graph Polynomial Arising from Community Structure (Extended Abstract).- Fast Exact Algorithms for Hamiltonicity in Claw-Free Graphs.- Maximum Series-Parallel Subgraph.- Low-Port Tree Representations.- Fully Dynamic Representations of Interval Graphs.- The Parameterized Complexity of Some Minimum Label Problems.- Exact and Parameterized Algorithms for Max Internal Spanning Tree.- An Exact Algorithm for Minimum Distortion Embedding.- Sub-coloring and Hypo-coloring Interval Graphs.- Parameterized Complexity of Generalized Domination Problems.- Connected Feedback Vertex Set in Planar Graphs.- Logical Locality Entails Frugal Distributed Computation over Graphs (Extended Abstract).- On Module-Composed Graphs.- An Even Simpler Linear-Time Algorithm for Verifying Minimum Spanning Trees.- The k-Disjoint Paths Problem on Chordal Graphs.- Local Algorithms for Edge Colorings in UDGs.- Directed Rank-Width and Displit Decomposition.- An Algorithmic Study of Switch Graphs.- Hardness Results and Efficient Algorithms for Graph Powers.- Graph Partitioning and Traffic Grooming with Bounded Degree Request Graph.- Injective Oriented Colourings.- Chordal Digraphs.- A New Intersection Model and Improved Algorithms for Tolerance Graphs.- Counting the Number of Matchings in Chordal and Chordal Bipartite Graph Classes.- Distance d-Domination Games.- Cycles, Paths, Connectivity and Diameter in Distance Graphs.- Smallest Odd Holes in Claw-Free Graphs (Extended Abstract).- Finding Induced Paths of Given Parity in Claw-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 Discrete Mathematics in Computer Science.