Clique-width: when hard does not mean impossible

DOI10.4230/LIPICS.STACS.2011.404zbMATH Open1230.68109MaRDI QIDQ3113705FDOQ3113705

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

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

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)

Cited In (11)

• 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
• MSO undecidability for hereditary classes of unbounded clique-width
• On width measures and topological problems on semi-complete digraphs
• Digraph width measures in parameterized algorithmics
• A unified approach to polynomial algorithms on graphs of bounded (bi-)rank-width
• Title not available (Why is that?)
• Clique is hard on average for regular resolution
• An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width

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)