Subset feedback vertex set in chordal and split graphs

DOI10.1007/S00453-019-00590-9MaRDI QIDQ6830318zbMATH OpenFDO

Authors Geevarghese Philip, Varun Rajan, Saket Saurabh, Prafullkumar Tale

Publication date 20 August 2019

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00453-019-00590-9

zbMATH Keywords

chordal graphsparameterized complexitysplit graphssubset feedback vertex set

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Cited in

(6)

• Difference determines the degree: structural kernelizations of component order connectivity
• Breaking the barrier 2ᵏ for subset feedback vertex set in chordal graphs
• Subset feedback vertex set in tournaments as fast as without the subset
• Solving subset feedback vertex set in chordal graphs faster than 2ᵏ
• Subset feedback vertex set and subset vertex cover on AT-free graphs
• Subset feedback vertex set in tournaments as fast as without the subset

This page was built for publication: Subset feedback vertex set in chordal and split graphs

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