Vertex disjoint paths on clique-width bounded graphs
From MaRDI portal
Publication:2503296
DOI10.1016/J.TCS.2006.02.026zbMATH Open1099.68078OpenAlexW2109121075MaRDI QIDQ2503296FDOQ2503296
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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
- Graph minors. XIII: The disjoint paths problem
- Linear time solvable optimization problems on graphs of bounded clique-width
- Upper bounds to the clique width of graphs
- Approximating clique-width and branch-width
- Deciding Clique-Width for Graphs of Bounded Tree-Width
- On the clique-width of some perfect graph classes
- Graph minors. II. Algorithmic aspects of tree-width
- On the Complexity of Timetable and Multicommodity Flow Problems
- The edge-disjoint paths problem is NP-complete for series-parallel graphs
- On simple characterizations of k-trees
- On the complexity of the disjoint paths problem
- A Linear Recognition Algorithm for Cographs
- Nearest common ancestors: a survey and a new algorithm for a distributed environment
- Clique partitions, graph compression and speeding-up algorithms
- \(k\)-NLC graphs and polynomial algorithms
- Edge dominating set and colorings on graphs with fixed clique-width
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- NLC\(_{2}\)-decomposition in polynomial time
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Graph-Theoretic Concepts in Computer Science
- Coloring powers of graphs of bounded clique-width.
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
- Digraph width measures in parameterized algorithmics
- The NLC-width and clique-width for powers of graphs of bounded tree-width
- On digraph width measures in parameterized algorithmics
- Algorithmic aspects of switch cographs
- 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
- Finding disjoint paths in split 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)
