Improved analysis of highest-degree branching for feedback vertex set

DOI10.1007/S00453-021-00815-WMaRDI QIDQ2041981zbMATH OpenOpenAlexFDO

Authors Yoichi Iwata, Yusuke Kobayashi

Publication date 26 July 2021

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1905.12233, https://drops.dagstuhl.de/opus/volltexte/2019/11483/

zbMATH Keywords

branch and boundmeasure and conquerparameterized complexityfeedback vertex set

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Recommendations

• scientific article; zbMATH DE number 7650230
• Faster deterministic \textsc{Feedback Vertex Set}
• On feedback vertex set: new measure and new structures
• A naive algorithm for feedback vertex set
• An improved exact algorithm for undirected feedback vertex set

Cites work

• scientific article; zbMATH DE number 512804 (Why is no real title available?)
• scientific article; zbMATH DE number 1467487 (Why is no real title available?)
• scientific article; zbMATH DE number 7286685 (Why is no real title available?)
• scientific article; zbMATH DE number 7650230 (Why is no real title available?)
• A measure \& conquer approach for the analysis of exact algorithms
• A naive algorithm for feedback vertex set
• Detecting Feedback Vertex Sets of Size k in O*(2.7^k) Time
• Exact exponential algorithms.
• Faster deterministic \textsc{Feedback Vertex Set}
• Faster parameterized algorithms using linear programming
• Half-integrality, LP-branching, and FPT algorithms
• 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
• Reducibility among combinatorial problems
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel

Cited in

(16)

• A parameterized complexity view on collapsing \(k\)-cores
• A parameterized algorithm for subset feedback vertex set in tournaments
• Exact algorithms for restricted subset feedback vertex set in chordal and split graphs
• Vertex cover and feedback vertex set above and below structural guarantees
• Faster algorithms and a smaller kernel for \textsc{Cliques or Trees Vertex Deletion}
• scientific article; zbMATH DE number 7650230 (Why is no real title available?)
• Kernelization for feedback vertex set via elimination distance to a forest
• Roman cycle hitting set
• Exact and parameterized algorithms for restricted subset feedback vertex set in chordal graphs
• Preprocessing to reduce the search space: antler structures for feedback vertex set
• Breaking the barrier 2ᵏ for subset feedback vertex set in chordal graphs
• Subset feedback vertex set in tournaments as fast as without the subset
• Parameterized Complexity of Fair Feedback Vertex Set Problem
• The structural complexity landscape of finding balance-fair shortest paths
• Improved FPT Algorithms for Deletion to Forest-Like Structures
• An improved deterministic parameterized algorithm for cactus vertex deletion

Describes a project that uses

Uses Software

• GitHub

This page was built for publication: Improved analysis of highest-degree branching for feedback vertex set

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