Fixed-parameter algorithms for DAG partitioning

DOI10.1016/j.dam.2016.12.002zbMath1355.05204arXiv1611.08809OpenAlexW2559697322MaRDI QIDQ507587

Sepp Hartung, René van Bevern, Ondřej Suchý, Falk Hüffner, André Nichterlein, Morgan Chopin, Robert Bredereck

Publication date: 6 February 2017

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1611.08809

zbMATH Keywords

graph algorithmsNP-hard problemlinear-time algorithmsalgorithm engineeringevaluating heuristicsmultiway cutpolynomial-time data reduction

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

Fractals for Kernelization Lower Bounds ⋮ Efficient algorithms for measuring the funnel-likeness of DAGs ⋮ Acyclic Digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Towards optimal and expressive kernelization for \(d\)-hitting set
• Infeasibility of instance compression and succinct PCPs for NP
• Simple and improved parameterized algorithms for multiterminal cuts
• Treewidth. Computations and approximations
• Which problems have strongly exponential complexity?
• A general method to speed up fixed-parameter-tractable algorithms
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• Applying modular decomposition to parameterized cluster editing problems
• A linear-time kernelization for the rooted \(k\)-leaf outbranching problem
• Parametrized complexity theory.
• Rounding algorithms for a geometric embedding of minimum multiway cut
• Simpler Linear-Time Kernelization for Planar Dominating Set
• Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs
• On a DAG Partitioning Problem
• New Races in Parameterized Algorithmics
• A Shortcut to (Sun)Flowers: Kernels in Logarithmic Space or Linear Time
• Emergence of Scaling in Random Networks
• Reflections on Multivariate Algorithmics and Problem Parameterization
• Kernelization: New Upper and Lower Bound Techniques
• The Complexity of Multiterminal Cuts
• Parameterized Complexity of DAG Partitioning
• Kernelization Lower Bounds by Cross-Composition
• Parameterized Algorithms
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• On the complexity of \(k\)-SAT

This page was built for publication: Fixed-parameter algorithms for DAG partitioning