Vertex disjoint paths on clique-width bounded graphs

DOI10.1016/J.TCS.2006.02.026MaRDI QIDQ2503296zbMATH OpenOpenAlexFDO

Authors Frank Gurski, Egon Wanke

Publication date 14 September 2006

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2006.02.026

zbMATH Keywords

clique-widthline graphstree-widthNLC-widthvertex disjoint pathsedge disjoint paths

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• LATIN 2004: Theoretical Informatics
• scientific article; zbMATH DE number 1151806
• General vertex disjoint paths in series-parallel graphs
• scientific article; zbMATH DE number 2044928
• Line graphs of bounded clique-width

Cites work

• scientific article; zbMATH DE number 1696534 (Why is no real title available?)
• scientific article; zbMATH DE number 1953082 (Why is no real title available?)
• scientific article; zbMATH DE number 2044924 (Why is no real title available?)
• scientific article; zbMATH DE number 2044928 (Why is no real title available?)
• scientific article; zbMATH DE number 1472167 (Why is no real title available?)
• scientific article; zbMATH DE number 1512682 (Why is no real title available?)
• A Linear Recognition Algorithm for Cographs
• Approximating clique-width and branch-width
• Clique partitions, graph compression and speeding-up algorithms
• Coloring powers of graphs of bounded clique-width.
• Deciding Clique-Width for Graphs of Bounded Tree-Width
• Edge dominating set and colorings on graphs with fixed clique-width
• Graph minors. II. Algorithmic aspects of tree-width
• Graph minors. XIII: The disjoint paths problem
• Graph-Theoretic Concepts in Computer Science
• Linear time solvable optimization problems on graphs of bounded clique-width
• NLC\(_{2}\)-decomposition in polynomial time
• Nearest common ancestors: a survey and a new algorithm for a distributed environment
• On simple characterizations of k-trees
• On the Complexity of Timetable and Multicommodity Flow Problems
• On the clique-width of some perfect graph classes
• On the complexity of the disjoint paths problem
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• The edge-disjoint paths problem is NP-complete for series-parallel graphs
• Upper bounds to the clique width of graphs
• \(k\)-NLC graphs and polynomial algorithms

Cited in

(16)

• Directed NLC-width
• Constrained-path labellings on graphs of bounded clique-width
• Comparing linear width parameters for directed graphs
• Line graphs of bounded clique-width
• The NLC-width and clique-width for powers of graphs of bounded tree-width
• Digraph width measures in parameterized algorithmics
• On digraph width measures in parameterized algorithmics
• Algorithmic aspects of switch cographs
• On \textsf{NC} algorithms for problems on bounded rank-width graphs
• Finding disjoint paths in split graphs
• Disjoint paths and connected subgraphs for \(H\)-free graphs
• Disjoint paths and connected subgraphs for \(H\)-free graphs
• Induced disjoint paths in circular-arc graphs in linear time
• Polynomial time algorithm for constructing vertex-disjoint paths in transposition graphs
• The behavior of clique-width under graph operations and graph transformations
• Polynomial algorithms for protein similarity search for restricted mRNA structures

This page was built for publication: Vertex disjoint paths on clique-width bounded graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2503296)