Improved analysis of highest-degree branching for feedback vertex set

DOI10.1007/S00453-021-00815-WOpenAlexW2998319348MaRDI QIDQ2041981FDOQ2041981

Yusuke Kobayashi, Yoichi Iwata

Publication date: 26 July 2021

Published in: Algorithmica (Search for Journal in Brave)

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

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

zbMATH Keywords

branch and boundmeasure and conquerparameterized complexityfeedback vertex set

Mathematics Subject Classification ID

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

Cites Work

• Reducibility among Combinatorial Problems
• A measure & conquer approach for the analysis of exact algorithms
• Exact exponential algorithms.
• Half-integrality, LP-branching, and FPT algorithms
• On Multiway Cut Parameterized above Lower Bounds
• Title not available (Why is that?)
• ON DISJOINT CYCLES
• Title not available (Why is that?)
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Improved algorithms for feedback vertex set problems
• The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
• Faster deterministic \textsc{Feedback Vertex Set}
• Faster Parameterized Algorithms Using Linear Programming
• On feedback vertex set: new measure and new structures
• Title not available (Why is that?)
• A naive algorithm for feedback vertex set
• Title not available (Why is that?)
• Detecting Feedback Vertex Sets of Size k in O*(2.7^k) Time
• Title not available (Why is that?)

Cited In (11)

• 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
• Title not available (Why is that?)
• Kernelization for feedback vertex set via elimination distance to a forest
• 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
• 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

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)