On the minimum feedback vertex set problem: Exact and enumeration algorithms
From MaRDI portal
Publication:958216
DOI10.1007/s00453-007-9152-0zbMath1170.68029OpenAlexW2047470084WikidataQ60488746 ScholiaQ60488746MaRDI QIDQ958216
Igor Razgon, Artem V. Pyatkin, Serge Gaspers, Fedor V. Fomin
Publication date: 2 December 2008
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-007-9152-0
exact exponential algorithmmaximum induced forestminimum feedback vertex setnumber of minimal feedback vertex sets
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Faster exact algorithms for some terminal set problems ⋮ Enumerating minimal connected dominating sets in graphs of bounded chordality ⋮ Minimal Dominating Sets in Graph Classes: Combinatorial Bounds and Enumeration ⋮ On the number of connected sets in bounded degree graphs ⋮ Circular convex bipartite graphs: feedback vertex sets ⋮ Maximal and maximum dissociation sets in general and triangle-free graphs ⋮ On Independent Sets and Bicliques in Graphs ⋮ Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms ⋮ On the feedback number of 3-uniform linear extremal hypergraphs ⋮ Largest chordal and interval subgraphs faster than \(2^n\) ⋮ Computing optimal Steiner trees in polynomial space ⋮ Minimal dominating sets in interval graphs and trees ⋮ Exact algorithms for maximum induced matching ⋮ Enumeration and maximum number of minimal connected vertex covers in graphs ⋮ Minimal dominating sets in graph classes: combinatorial bounds and enumeration ⋮ On the Number of Connected Sets in Bounded Degree Graphs ⋮ Feedback vertex sets on restricted bipartite graphs ⋮ MIP formulations for induced graph optimization problems: a tutorial ⋮ Large Induced Subgraphs via Triangulations and CMSO ⋮ Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree} ⋮ Solving target set selection with bounded thresholds faster than \(2^n\) ⋮ Hierarchical cycle-tree packing model for optimal \(K\)-core attack ⋮ On independent sets and bicliques in graphs ⋮ Covering and packing in linear space ⋮ Sharp separation and applications to exact and parameterized algorithms ⋮ On the maximum number of maximum dissociation sets in trees with given dissociation number ⋮ Enumerating Minimal Tropical Connected Sets ⋮ Feedback Vertex Sets in Tournaments ⋮ Branch and recharge: exact algorithms for generalized domination ⋮ Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem ⋮ Subset feedback vertex sets in chordal graphs ⋮ An improved parameterized algorithm for the independent feedback vertex set problem ⋮ Enumerating minimal subset feedback vertex sets ⋮ On the number of minimal dominating sets on some graph classes ⋮ On feedback vertex set: new measure and new structures ⋮ Two Hardness Results on Feedback Vertex Sets ⋮ Solving Target Set Selection with Bounded Thresholds Faster than 2^n ⋮ Inclusion/exclusion meets measure and conquer ⋮ Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs ⋮ Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms ⋮ On the Number of Minimal Separators in Graphs ⋮ An Improved Exact Algorithm for Undirected Feedback Vertex Set ⋮ Circular Convex Bipartite Graphs: Feedback Vertex Set ⋮ An improved exact algorithm for undirected feedback vertex set
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Enumerating maximal independent sets with applications to graph colouring.
- A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
- A greedy randomized adaptive search procedure for the feedback vertex set problem
- On enumerating all minimal solutions of feedback problems
- Solving the feedback vertex set problem on undirected graphs
- Wavelength Conversion in Optical Networks
- Finding a Minimum Feedback Vertex Set in Time $\mathcal{O} (1.7548^n)$
- Measure and conquer
- Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings
- Algorithms for maximum independent sets
- Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
- Approximating Minimum Subset Feedback Sets in Undirected Graphs with Applications
- On the number of maximal bipartite subgraphs of a graph
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- Algorithms and Data Structures
- Theoretical Computer Science
- A Min-Max Theorem on Feedback Vertex Sets
- Automata, Languages and Programming
- Computing and Combinatorics
- Exact Computation of Maximum Induced Forest
- Algorithms and Computation
- On cliques in graphs
