Graph-Theoretic Concepts in Computer Science : 35th International Workshop, WG 2009, Montpellier, France, June 24-26, 2009, Revised Papers / edited by Christophe Paul, Michel Habib.

Format:

Book

Contributor:

Paul, Christophe, editor.

Habib, M. (Michel), editor.

SpringerLink (Online service)

Series:

Computer Science (Springer-11645)

LNCS sublibrary. Theoretical computer science and general issues ; SL 1, 5911.

Theoretical Computer Science and General Issues ; 5911

Language:

English

Subjects (All):

Computer science--Mathematics.

Computer science.

Geometry.

Algorithms.

Data structures (Computer science).

Discrete Mathematics in Computer Science.

Symbolic and Algebraic Manipulation.

Algorithm Analysis and Problem Complexity.

Data Structures.

Local Subjects:

Discrete Mathematics in Computer Science.

Geometry.

Algorithms.

Symbolic and Algebraic Manipulation.

Algorithm Analysis and Problem Complexity.

Data Structures.

Physical Description:

1 online resource (XIII, 353 pages).

Edition:

First edition 2010.

Contained In:

Springer eBooks

Place of Publication:

Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2010.

System Details:

text file PDF

Summary:

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.

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.

Other Format:

Printed edition:

ISBN:

978-3-642-11409-0

9783642114090

Access Restriction:

Restricted for use by site license.