An Improved Exact Algorithm for Undirected Feedback Vertex Set

DOI10.1007/978-3-319-03780-6_14zbMath1407.68375OpenAlexW2402064113MaRDI QIDQ2867116

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

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

Related Items

Circular convex bipartite graphs: feedback vertex sets ⋮ Large Induced Subgraphs via Triangulations and CMSO ⋮ An improved FPT algorithm for almost forest deletion problem ⋮ An improved exact algorithm for TSP in graphs of maximum degree 4

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Improved algorithms for feedback vertex set problems
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• Approximating minimum feedback sets and multicuts in directed graphs
• Fast algorithms for max independent set
• A Refined Exact Algorithm for Edge Dominating Set
• A fixed-parameter algorithm for the directed feedback vertex set problem
• A measure & conquer approach for the analysis of exact algorithms
• On Feedback Vertex Set New Measure and New Structures
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• Computing and Combinatorics
• Exact Computation of Maximum Induced Forest