Exploiting Restricted Linear Structure to Cope with the Hardness of Clique-Width

DOI10.1007/978-3-642-13562-0_26zbMATH Open1284.68280OpenAlexW1575418443MaRDI QIDQ3569083FDOQ3569083

Authors: Pinar Heggernes, Daniel Meister, Udi Rotics 

Publication date: 17 June 2010

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-13562-0_26

Recommendations

• Clique-width: when hard does not mean impossible
• Clique-width minimization is NP-hard
• scientific article; zbMATH DE number 1262783
• Graph-Theoretic Concepts in Computer Science
• Approximating rank-width and clique-width quickly
• Query efficient implementation of graphs of bounded clique-width
• Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
• Approximating clique-width and branch-width

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cited In (4)

• A new representation of proper interval graphs with an application to clique-width
• From Tree-Width to Clique-Width: Excluding a Unit Interval Graph
• Computing the clique-width of large path powers in linear time via a new characterisation of clique-width
• Clique-width of full bubble model graphs

This page was built for publication: Exploiting Restricted Linear Structure to Cope with the Hardness of Clique-Width

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