Linear kernels for outbranching problems in sparse digraphs

DOI10.1007/S00453-016-0244-6MaRDI QIDQ2408200zbMATH OpenOpenAlexWikidataFDO

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

Publication date 10 October 2017

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

\( H\)-minor-free graphsbounded expansionkernelizationoutbranchingsparse graph

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 6784970
• Kernel(s) for problems with no kernel
• A linear-time kernelization for the rooted k-leaf outbranching problem
• \(\text{Kernel}(s)\) for problems with no kernel: on out-trees with many leaves
• A linear-time kernelization for the rooted \(k\)-leaf outbranching problem

Cites work

• (Meta) Kernelization
• A c^k n 5-approximation algorithm for treewidth
• A subexponential parameterized algorithm for subset TSP on planar graphs
• Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
• Bidimensionality and kernels
• Contraction decomposition in \(h\)-minor-free graphs and algorithmic applications
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Graph-Theoretic Concepts in Computer Science
• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 6784970 (Why is no real title available?)
• Kernel(s) for problems with no kernel
• Kernelization and Sparseness: the case of Dominating Set
• Kernelization using structural parameters on sparse graph classes
• Local tree-width, excluded minors, and approximation algorithms
• Lower bounds based on the exponential time hypothesis
• Minimum leaf out-branching and related problems
• Network sparsification for Steiner problems on planar and bounded-genus graphs
• NP-completeness and degree restricted spanning trees
• On complexity of minimum leaf out-branching problem
• On finding directed trees with many leaves
• Parametrized complexity theory.
• Polynomial-time data reduction for dominating set
• Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Sparsity. Graphs, structures, and algorithms
• Subexponential algorithms for partial cover problems
• Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs
• Subexponential parameterized odd cycle transversal on planar graphs
• Subexponential-time parameterized algorithm for Steiner tree on planar graphs
• The Rectilinear Steiner Tree Problem is NP-Complete

Cited in

(6)

• Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
• Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
• Linear Vertex-kernels for Several Dense Ranking r -Constraint Satisfaction Problems
• Algorithms for \(k\)-internal out-branching and \(k\)-tree in bounded degree graphs
• scientific article; zbMATH DE number 6784970 (Why is no real title available?)
• \(\text{Kernel}(s)\) for problems with no kernel: on out-trees with many leaves

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

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