Subset feedback vertex set in chordal and split graphs
From MaRDI portal
Publication:5919404
DOI10.1007/978-3-030-17402-6_30zbMath1429.68198arXiv1901.02209OpenAlexW2963978247WikidataQ127781153 ScholiaQ127781153MaRDI QIDQ5919404
Geevarghese Philip, Prafullkumar Tale, Varun Rajan, Saket Saurabh
Publication date: 6 February 2020
Published in: Algorithmica, Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1901.02209
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (6)
Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ 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 ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ Subset feedback vertex set on graphs of bounded independent set size
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
- Enumerating minimal subset feedback vertex sets
- Exact exponential algorithms.
- A kernelization algorithm for \(d\)-hitting set
- The splittance of a graph
- A randomized polynomial kernel for subset feedback vertex set
- Algorithmic graph theory and perfect graphs
- Faster exact algorithms for some terminal set problems
- Subset feedback vertex sets in chordal graphs
- Hitting Forbidden Minors: Approximation and Kernelization
- Subset Feedback Vertex Set Is Fixed-Parameter Tractable
- An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
- Linear Time Parameterized Algorithms for S <scp>ubset</scp> F <scp>eedback</scp> V <scp>ertex</scp> S <scp>et</scp>
- Subquadratic Kernels for Implicit 3-H <scp>itting</scp> S <scp>et</scp> and 3-S <scp>et</scp> P <scp>acking</scp> Problems
- Kernelization
- Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable
- Exact Algorithms via Monotone Local Search
- Half-integrality, LP-branching and FPT Algorithms
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
- Parameterized Algorithms
This page was built for publication: Subset feedback vertex set in chordal and split graphs