Beyond bidimensionality: parameterized subexponential algorithms on directed graphs

DOI10.1016/j.ic.2013.11.006zbMath1433.68290OpenAlexW1533217239WikidataQ60488413 ScholiaQ60488413MaRDI QIDQ391650

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

Publication date: 10 January 2014

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2013.11.006

zbMATH Keywords

directed graphgraph algorithmsparameterized algorithmssubexponential running time

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Parameterized complexity, tractability and kernelization (68Q27)

Related Items

Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering ⋮ Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ Unnamed Item ⋮ Linear kernels for outbranching problems in sparse digraphs ⋮ Adapting the Directed Grid Theorem into an FPT Algorithm ⋮ A \(2^{O(k)}n\) algorithm for \(k\)-cycle in minor-closed graph families

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Catalan structures and dynamic programming in \(H\)-minor-free graphs
• The dag-width of directed graphs
• Subexponential parameterized algorithms
• A new algorithm for finding trees with many leaves
• Finding odd cycle transversals.
• Improved upper bounds for vertex cover
• FPT algorithms and kernels for the directed \(k\)-leaf problem
• Approximation algorithms for treewidth
• Linearity of grid minors in treewidth with applications through bidimensionality
• Improved algorithms for feedback vertex set problems
• Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem
• Minimum leaf out-branching and related problems
• Quickly excluding a planar graph
• Which problems have strongly exponential complexity?
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Directed tree-width
• Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
• Contraction obstructions for treewidth
• Parametrized complexity theory.
• Subexponential Parameterized Algorithm for Computing the Cutwidth of a Semi-complete Digraph
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs
• Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament
• Tight bounds and a fast FPT algorithm for directed Max-Leaf Spanning Tree
• Kernel(s) for problems with no kernel
• Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Fast FAST
• A Linear Vertex Kernel for Maximum Internal Spanning Tree
• On Finding Directed Trees with Many Leaves
• Approximation algorithms for NP-complete problems on planar graphs
• Color-coding
• Spanning Directed Trees with Many Leaves
• Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time

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