An Improved Exact Algorithm for Undirected Feedback Vertex Set

DOI10.1007/978-3-319-03780-6_14MaRDI QIDQ2867116zbMATH OpenOpenAlexFDO

Authors Mingyu Xiao, Hiroshi Nagamochi

Publication date 10 December 2013

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-03780-6_14

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• An improved exact algorithm for undirected feedback vertex set
• Improved Algorithms for the Feedback Vertex Set Problems
• Improved algorithms for feedback vertex set problems
• scientific article; zbMATH DE number 1979503
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• Solving the feedback vertex set problem on undirected graphs
• An improved parameterized algorithm for the independent feedback vertex set problem
• An improved FPT algorithm for independent feedback vertex set
• An improved FPT algorithm for independent feedback vertex set
• Improved Algorithms and Combinatorial Bounds for Independent Feedback Vertex Set

Cites work

• scientific article; zbMATH DE number 6118220 (Why is no real title available?)
• scientific article; zbMATH DE number 571325 (Why is no real title available?)
• scientific article; zbMATH DE number 3405712 (Why is no real title available?)
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• A fixed-parameter algorithm for the directed feedback vertex set problem
• A measure \& conquer approach for the analysis of exact algorithms
• A refined exact algorithm for edge dominating set
• Approximating minimum feedback sets and multicuts in directed graphs
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Computing and Combinatorics
• Exact Computation of Maximum Induced Forest
• Fast algorithms for max independent set
• Improved algorithms for feedback vertex set problems
• On feedback vertex set new measure and new structures
• On the minimum feedback vertex set problem: Exact and enumeration algorithms

Cited in

(12)

• An improved exact algorithm for TSP in graphs of maximum degree 4
• scientific article; zbMATH DE number 970357 (Why is no real title available?)
• Exact computation of minimum feedback vertex sets with relational algebra
• An improved FPT algorithm for almost forest deletion problem
• Circular convex bipartite graphs: feedback vertex sets
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• An improved exact algorithm for undirected feedback vertex set
• Exact Computation of Maximum Induced Forest
• scientific article; zbMATH DE number 1979503 (Why is no real title available?)
• Improved Algorithms for the Feedback Vertex Set Problems
• A fixed-parameter algorithm for the directed feedback vertex set problem
• Large Induced Subgraphs via Triangulations and CMSO

This page was built for publication: An Improved Exact Algorithm for Undirected Feedback Vertex Set

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