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

DOI10.1016/j.tcs.2023.114326MaRDI QIDQ6140360

Mingyu Xiao, Tian Bai

Publication date: 2 January 2024

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

chordal graphssplit graphsparameterized algorithmsexact exponential algorithmssubset feedback vertex set

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• 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
• The Representation of a Graph by Set Intersections
• Subset feedback vertex set in chordal and split graphs

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