Exact and parameterized algorithms for restricted subset feedback vertex set in chordal graphs

DOI10.1007/978-3-031-20350-3_20MaRDI QIDQ6111961

Tian Bai, Mingyu Xiao

Publication date: 4 August 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

zbMATH Keywords

chordal graphsparameterized algorithmsexact exponential algorithmssubset feedback vertex set

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

A parameterized algorithm for subset feedback vertex set in tournaments

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Enumerating minimal subset feedback vertex sets
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Improved upper bounds for vertex cover
• On rigid circuit graphs
• The maximum k-colorable subgraph problem for chordal graphs
• A randomized polynomial kernel for subset feedback vertex set
• A characterisation of rigid circuit graphs
• Exact algorithms for maximum independent set
• Improved analysis of highest-degree branching for feedback vertex set
• Faster exact algorithms for some terminal set problems
• Incidence matrices and interval graphs
• Subset feedback vertex sets in chordal graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Half-integrality, LP-branching, and FPT Algorithms
• Algorithmic Aspects of Vertex Elimination on Graphs
• An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
• Properties of vertex packing and independence system polyhedra
• Reducibility among Combinatorial Problems
• Exact Algorithms via Monotone Local Search
• Parameterized and Exact Computation
• Data reduction and exact algorithms for clique cover
• Subset feedback vertex set in chordal and split graphs

This page was built for publication: Exact and parameterized algorithms for restricted subset feedback vertex set in chordal graphs