On \textsf{NC} algorithms for problems on bounded rank-width graphs

DOI10.1016/j.ipl.2018.07.007zbMath1478.68229OpenAlexW2883517495MaRDI QIDQ1799577

Yanyan Li

Publication date: 19 October 2018

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2018.07.007

zbMATH Keywords

NP-completenessparallel algorithmsclique-widthrank-width

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Unnamed Item
• \(k\)-NLC graphs and polynomial algorithms
• Linear time solvable optimization problems on graphs of bounded clique-width
• Approximating clique-width and branch-width
• Vertex disjoint paths on clique-width bounded graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Approximating rank-width and clique-width quickly
• Counting Euler Tours in Undirected Bounded Treewidth Graphs
• Computational Complexity
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: On \textsf{NC} algorithms for problems on bounded rank-width graphs