Subset feedback vertex sets in chordal graphs

DOI10.1016/j.jda.2013.09.005zbMath1298.05302OpenAlexW2110960146MaRDI QIDQ2447531

Dieter Kratsch, Reza Saei, Pinar Heggernes, Petr A. Golovach

Publication date: 28 April 2014

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2013.09.005

zbMATH Keywords

chordal graphsubset feedback vertex setexact exponential-time algorithmmaximum number of minimal subset feedback vertex sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Faster exact algorithms for some terminal set problems, Enumerating minimal connected dominating sets in graphs of bounded chordality, Linear-Time Generation of Random Chordal Graphs, Minimal dominating sets in interval graphs and trees, Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage, Enumeration and maximum number of minimal connected vertex covers in graphs, A parameterized algorithm for subset feedback vertex set in tournaments, Exact and parameterized algorithms for restricted subset feedback vertex set in chordal graphs, Exact algorithms for restricted subset feedback vertex set in chordal and split graphs, Unnamed Item, Enumerating Minimal Tropical Connected Sets, Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage, Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs, Computing subset transversals in \(H\)-free graphs, Subset feedback vertex set in chordal and split graphs, Subset feedback vertex set on graphs of bounded independent set size, Node multiway cut and subset feedback vertex set on graphs of bounded mim-width

Uses Software

• symrcm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exact exponential algorithms.
• On rigid circuit graphs
• Feedback vertex set on AT-free graphs
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• The complexity of generalized clique covering
• On enumerating all minimal solutions of feedback problems
• Efficient graph representations
• Algorithmic graph theory and perfect graphs
• Incidence matrices and interval graphs
• Maximum Number of Minimal Feedback Vertex Sets in Chordal Graphs and Cographs
• Subset Feedback Vertex Set Is Fixed-Parameter Tractable
• Enumeration of Minimal Dominating Sets and Variants
• Finding Induced Subgraphs via Minimal Triangulations
• Feedback Vertex Sets in Tournaments
• An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
• An Exact Algorithm for Subset Feedback Vertex Set on Chordal Graphs
• Combinatorial bounds via measure and conquer
• Enumerating Minimal Subset Feedback Vertex Sets
• On cliques in graphs