Linear kernels for outbranching problems in sparse digraphs

DOI10.1007/s00453-016-0244-6zbMath1378.68063OpenAlexW2964213279WikidataQ59603710 ScholiaQ59603710MaRDI QIDQ2408200

Łukasz Kowalik, Marthe Bonamy, Michał Pilipczuk, Arkadiusz Socała

Publication date: 10 October 2017

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-016-0244-6

zbMATH Keywords

kernelizationsparse graphbounded expansion\( H\)-minor-free graphsoutbranching

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
• Sparsity. Graphs, structures, and algorithms
• On complexity of minimum leaf out-branching problem
• Minimum leaf out-branching and related problems
• NP-completeness and degree restricted spanning trees
• Subexponential algorithms for partial cover problems
• Parametrized complexity theory.
• Local tree-width, excluded minors, and approximation algorithms
• A $c^k n$ 5-Approximation Algorithm for Treewidth
• Kernelization Using Structural Parameters on Sparse Graph Classes
• Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs
• Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
• Kernel(s) for problems with no kernel
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Polynomial-time data reduction for dominating set
• On Finding Directed Trees with Many Leaves
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Kernelization and Sparseness: the case of Dominating Set
• Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs
• (Meta) Kernelization
• Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth
• A subexponential parameterized algorithm for Subset TSP on planar graphs
• Bidimensionality and Geometric Graphs
• Contraction decomposition in h-minor-free graphs and algorithmic applications
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Graph-Theoretic Concepts in Computer Science
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Linear kernels for outbranching problems in sparse digraphs