Clique-width: when hard does not mean impossible

DOI10.4230/LIPICS.STACS.2011.404MaRDI QIDQ3113705zbMATH OpenFDO

Authors Robert Ganian, Petr Hliněný, Jan Obdržálek

Publication date 23 January 2012

Full work available at URL http://subs.emis.de/LIPIcs/frontdoor_2221.html

zbMATH Keywords

edge-disjoint pathsclique-widthbi-rank-widthminimum leaf out-branchingminimum leaf spanning tree

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Clique-width: on the price of generality
• Digraph width measures in parameterized algorithmics
• Algorithmic lower bounds for problems parameterized by clique-width
• Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
• Intractability of clique-width parameterizations

Cited in

(10)

• Directed NLC-width
• Are there any good digraph width measures?
• Exploiting Restricted Linear Structure to Cope with the Hardness of Clique-Width
• Fast exact algorithms for some connectivity problems parameterized by clique-width
• On width measures and topological problems on semi-complete digraphs
• MSO undecidability for hereditary classes of unbounded clique-width
• Digraph width measures in parameterized algorithmics
• A unified approach to polynomial algorithms on graphs of bounded (bi-)rank-width
• scientific article; zbMATH DE number 7029306 (Why is no real title available?)
• Clique is hard on average for regular resolution

This page was built for publication: Clique-width: when hard does not mean impossible

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