Beyond bidimensionality: parameterized subexponential algorithms on directed graphs

DOI10.4230/LIPICS.STACS.2010.2459MaRDI QIDQ3113754zbMATH OpenFDO

Authors Frederic Dorn, Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh

Publication date 23 January 2012

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

zbMATH Keywords

directed graphsout-branchinginternal out-branchingparameterized subexponential algorithms

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
• scientific article; zbMATH DE number 6784970
• Subexponential Parameterized Algorithms
• Subexponential parameterized algorithms
• Linear kernels for outbranching problems in sparse digraphs

Cited in

(8)

• Confronting intractability via parameters
• Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
• Faster parameterized algorithms for minor containment
• Faster approximation schemes and parameterized algorithms on (odd-)\(H\)-minor-free graphs
• Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
• Subexponential parameterized algorithms for graphs of polynomial growth
• Parameterized algorithms for non-separating trees and branchings in digraphs
• What's next? Future directions in parameterized complexity

This page was built for publication: Beyond bidimensionality: parameterized subexponential algorithms on directed graphs

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