Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage

DOI10.1007/s00453-023-01149-5OpenAlexW4384133395MaRDI QIDQ6119835

Spyridon Tzimas, Charis Papadopoulos

Publication date: 25 March 2024

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-023-01149-5

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• 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
• Finding disjoint paths in split graphs
• The longest path problem has a polynomial solution on interval graphs
• Computing weighted subset transversals in \(H\)-free graphs
• On the parameterized complexity of multiple-interval graph problems
• Clustering and domination in perfect graphs
• Intersection graphs of paths in a tree
• Hamiltonian circuits in interval graph generalizations
• A recognition algorithm for the intersection graphs of directed paths in directed trees
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The complexity of generalized clique covering
• Efficient graph representations
• A randomized polynomial kernel for subset feedback vertex set
• A characterisation of rigid circuit graphs
• The separator theorem for rooted directed vertex graphs
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• On the tractability of optimization problems on \(H\)-graphs
• Mim-width. II. The feedback vertex set problem
• Intersection graphs of non-crossing paths
• Subset feedback vertex set on graphs of bounded independent set size
• Mim-width. III. Graph powers and generalized distance domination problems
• The vertex leafage of chordal graphs
• Subset feedback vertex sets in chordal graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Subset Feedback Vertex Set Is Fixed-Parameter Tractable
• Polynomial-Time Algorithm for the Leafage of Chordal Graphs
• Node-Deletion Problems on Bipartite Graphs
• Dominating Sets in Chordal Graphs
• The leafage of a chordal graph
• Reducibility among Combinatorial Problems
• Parameterized Algorithms
• Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs
• Computing subset transversals in \(H\)-free graphs
• Subset feedback vertex set in chordal and split graphs
• Node multiway cut and subset feedback vertex set on graphs of bounded mim-width

This page was built for publication: Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage