scientific article; zbMATH DE number 7286685

DOI10.4230/LIPICS.SEA.2018.12MaRDI QIDQ5140722zbMATH OpenFDO

Authors Krzysztof Kiljan, Marcin Pilipczuk

Publication date 16 December 2020

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

zbMATH Keywords

empirical evaluation of algorithmsfeedback vertex set

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27)

Recommendations

• Parameterized and Exact Computation
• Fixed parameterized algorithms for generalized feedback vertex set problems
• Improved Algorithms for the Feedback Vertex Set Problems
• Improved algorithms for feedback vertex set problems
• Parameterized algorithms for generalizations of directed feedback vertex set
• Parameterized algorithms for generalizations of directed feedback vertex set
• Faster fixed parameter tractable algorithms for finding feedback vertex sets
• An improved parameterized algorithm for the independent feedback vertex set problem
• Simultaneous feedback vertex set: a parameterized perspective

Cites work

• A 4k^2 kernel for feedback vertex set
• A cubic kernel for feedback vertex set and loop cutset
• A naive algorithm for feedback vertex set
• An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
• An augmenting path algorithm for linear matroid parity
• Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Faster deterministic \textsc{Feedback Vertex Set}
• Faster fixed parameter tractable algorithms for finding feedback vertex sets
• Half-integrality, LP-branching, and FPT algorithms
• scientific article; zbMATH DE number 512804 (Why is no real title available?)
• scientific article; zbMATH DE number 1467487 (Why is no real title available?)
• Improved algorithms for feedback vertex set problems
• Linear-time kernelization for feedback vertex set
• ON DISJOINT CYCLES
• On feedback vertex set new measure and new structures
• Parameterized algorithms
• Parameterized and Exact Computation
• Reducibility among combinatorial problems
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• The PACE 2017 parameterized algorithms and computational experiments challenge: the second iteration
• The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel

Cited in

(7)

• Improved analysis of highest-degree branching for feedback vertex set
• The PACE 2018 parameterized algorithms and computational experiments challenge: the third iteration
• scientific article; zbMATH DE number 7651198 (Why is no real title available?)
• Exploiting Database Management Systems and Treewidth for Counting
• Aspmc: new frontiers of algebraic answer set counting
• Cluster editing parameterized above modification-disjoint P₃-packings
• Cluster editing parameterized above modification-disjoint P₃-Packings

Describes a project that uses

Uses Software

• GitHub

This page was built for publication:

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