Vertex disjoint paths on clique-width bounded graphs

DOI10.1016/j.tcs.2006.02.026zbMath1099.68078OpenAlexW2109121075MaRDI QIDQ2503296

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

line graphsclique-widthtree-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)

Related Items (15)

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

Cites Work

• Nearest common ancestors: a survey and a new algorithm for a distributed environment
• \(k\)-NLC graphs and polynomial algorithms
• On simple characterizations of k-trees
• Edge dominating set and colorings on graphs with fixed clique-width
• Graph minors. XIII: The disjoint paths problem
• Clique partitions, graph compression and speeding-up algorithms
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• On the complexity of the disjoint paths problem
• Approximating clique-width and branch-width
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• A Linear Recognition Algorithm for Cographs
• Graph minors. II. Algorithmic aspects of tree-width
• On the Complexity of Timetable and Multicommodity Flow Problems
• Deciding Clique-Width for Graphs of Bounded Tree-Width
• NLC₂-DECOMPOSITION IN POLYNOMIAL TIME
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• Graph-Theoretic Concepts in Computer Science
• Graph-Theoretic Concepts in Computer Science
• The edge-disjoint paths problem is NP-complete for series-parallel graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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