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) Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)

Cited in

(3)

• Breaking the barrier 2ᵏ for subset feedback vertex set in chordal graphs
• Subset feedback vertex set in tournaments as fast as without the subset
• Difference determines the degree: structural kernelizations of component order connectivity

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)