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 (17)

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

This page was built for publication: Subset feedback vertex sets in chordal graphs