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

DOI10.1007/S00453-023-01149-5MaRDI QIDQ6119835zbMATH OpenOpenAlexFDO

Authors Charis Papadopoulos, Spyridon Tzimas

Publication date 25 March 2024

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

Mathematics Subject Classification ID

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

Cites work

• A characterisation of rigid circuit graphs
• A randomized polynomial kernel for subset feedback vertex set
• A recognition algorithm for the intersection graphs of directed paths in directed trees
• Clustering and domination in perfect graphs
• Computing subset transversals in \(H\)-free graphs
• Computing weighted subset transversals in \(H\)-free graphs
• Dominating Sets in Chordal Graphs
• Efficient graph representations
• Enumerating minimal subset feedback vertex sets
• Finding disjoint paths in split graphs
• Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
• Graph theory
• Hamiltonian circuits in interval graph generalizations
• scientific article; zbMATH DE number 1496855 (Why is no real title available?)
• Intersection graphs of non-crossing paths
• Intersection graphs of paths in a tree
• Mim-width. II. The feedback vertex set problem
• Mim-width. III. Graph powers and generalized distance domination problems
• Node multiway cut and subset feedback vertex set on graphs of bounded mim-width
• Node-Deletion Problems on Bipartite Graphs
• On the parameterized complexity of multiple-interval graph problems
• 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
• Parameterized algorithms
• Polynomial-Time Algorithm for the Leafage of Chordal Graphs
• Reducibility among combinatorial problems
• Subset feedback vertex set on graphs of bounded independent set size
• Subset feedback vertex sets in chordal graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The complexity of generalized clique covering
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The leafage of a chordal graph
• The longest path problem has a polynomial solution on interval graphs
• The separator theorem for rooted directed vertex graphs
• The vertex leafage of chordal graphs

Cited in

(3)

• Parameterized algorithms for Steiner tree and (connected) dominating set on path graphs
• Finding maximum matchings in RDV graphs efficiently
• Subset feedback vertex set and subset vertex cover on AT-free graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6119835)