Subset feedback vertex sets in chordal graphs

DOI10.1016/J.JDA.2013.09.005MaRDI QIDQ2447531zbMATH OpenOpenAlexFDO

Authors Pinar Heggernes, Dieter Kratsch, Reza Saei, 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

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

Recommendations

• An exact algorithm for subset feedback vertex set on chordal graphs
• Exact and parameterized algorithms for restricted subset feedback vertex set in chordal graphs
• Subset feedback vertex set on graphs of bounded independent set size
• Subset feedback vertex set on graphs of bounded independent set size
• Chord-set subgraphs of chordal graphs
• Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage
• Maximum Number of Minimal Feedback Vertex Sets in Chordal Graphs and Cographs
• Feedback vertex sets and cyclically reducible graphs

Cites work

• scientific article; zbMATH DE number 3816913 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• Algorithmic graph theory and perfect graphs
• 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
• Efficient graph representations
• Enumerating minimal subset feedback vertex sets
• Enumeration of minimal dominating sets and variants
• Exact exponential algorithms.
• Feedback vertex set on AT-free graphs
• Feedback vertex sets in tournaments
• Finding induced subgraphs via minimal triangulations
• Incidence matrices and interval graphs
• Maximum Number of Minimal Feedback Vertex Sets in Chordal Graphs and Cographs
• On cliques in graphs
• On enumerating all minimal solutions of feedback problems
• On rigid circuit graphs
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• The complexity of generalized clique covering

Cited in

(19)

• Enumerating minimal subset feedback vertex sets
• A parameterized algorithm for subset feedback vertex set in tournaments
• Node multiway cut and subset feedback vertex set on graphs of bounded mim-width
• Exact algorithms for restricted subset feedback vertex set in chordal and split graphs
• Enumerating minimal connected dominating sets in graphs of bounded chordality
• Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage
• Enumerating minimal subset feedback vertex sets
• Enumeration and maximum number of minimal connected vertex covers in graphs
• An exact algorithm for subset feedback vertex set on chordal graphs
• Exact and parameterized algorithms for restricted subset feedback vertex set in chordal graphs
• Subset feedback vertex set on graphs of bounded independent set size
• Subset feedback vertex set on graphs of bounded independent set size
• Enumerating Minimal Tropical Connected Sets
• Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage
• Minimal dominating sets in interval graphs and trees
• Computing subset transversals in \(H\)-free graphs
• Maximum Number of Minimal Feedback Vertex Sets in Chordal Graphs and Cographs
• Linear-time generation of random chordal graphs
• Faster exact algorithms for some terminal set problems

Describes a project that uses

Uses Software

• symrcm

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

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