Graph-Theoretic Concepts in Computer Science : 31st International Workshop, WG 2005, Metz, France, June 23-25, 2005, Revised Selected Papers / edited by Dieter Kratsch.

Format:

Book

Contributor:

Kratsch, D. (Dieter), editor.

SpringerLink (Online service)

Series:

Computer Science (Springer-11645)

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

Theoretical Computer Science and General Issues ; 3787

Language:

English

Subjects (All):

Computers.

Computer simulation.

Algorithms.

Computer science--Mathematics.

Computer science.

Numerical analysis.

Data structures (Computer science).

Theory of Computation.

Simulation and Modeling.

Algorithm Analysis and Problem Complexity.

Discrete Mathematics in Computer Science.

Numeric Computing.

Data Structures.

Local Subjects:

Theory of Computation.

Simulation and Modeling.

Algorithm Analysis and Problem Complexity.

Discrete Mathematics in Computer Science.

Numeric Computing.

Data Structures.

Physical Description:

1 online resource (XIV, 478 pages).

Edition:

First edition 2005.

Contained In:

Springer eBooks

Place of Publication:

Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2005.

System Details:

text file PDF

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.

Other Format:

Printed edition:

ISBN:

978-3-540-31468-4

9783540314684

Access Restriction:

Restricted for use by site license.