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

DOI10.1016/J.IPL.2018.07.007MaRDI QIDQ1799577zbMATH OpenOpenAlexFDO

Authors 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

clique-widthNP-completenessparallel algorithmsrank-width

Mathematics Subject Classification ID

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

Recommendations

• A unified approach to polynomial algorithms on graphs of bounded (bi-)rank-width
• Better polynomial algorithms on graphs of bounded rank-width
• Linear-time algorithms for graphs of bounded rankwidth: a fresh look using game theory (extended abstract)
• Solving problems on graphs of high rank-width
• Solving problems on graphs of high rank-width
• Algorithms for solving problems on graphs of bounded pathwidth
• Rank-width: algorithmic and structural results
• A bound on the pathwidth of sparse graphs with applications to exact algorithms
• Classes of graphs with low complexity: the case of classes with bounded linear rankwidth
• scientific article; zbMATH DE number 2044928

Cites work

• \(k\)-NLC graphs and polynomial algorithms
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Approximating clique-width and branch-width
• Approximating rank-width and clique-width quickly
• Computational Complexity
• Counting Euler tours in undirected bounded treewidth graphs
• Graph minors. II. Algorithmic aspects of tree-width
• scientific article; zbMATH DE number 1142315 (Why is no real title available?)
• Linear time solvable optimization problems on graphs of bounded clique-width
• Vertex disjoint paths on clique-width bounded graphs

Cited in

(2)

• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• Canonizing graphs of bounded rank-width in parallel via Weisfeiler-Leman

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

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