Domination and cut problems on chordal graphs with bounded leafage

DOI10.4230/LIPICS.IPEC.2022.14MaRDI QIDQ6968998zbMATH OpenFDO

Authors Esther Galby, Dániel Marx, Philipp Schepper, Roohani Sharma, Prafullkumar Tale

Publication date 23 June 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.IPEC.2022.14

zbMATH Keywords

chordal graphsdominating setFPT algorithmsleafagemulticut with undeletable terminalsmultiway cut with undeletable terminals

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Algorithms in computer science (68Wxx)

Cites work

• A characterisation of rigid circuit graphs
• A Characterization of Comparability Graphs and of Interval Graphs
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• A width parameter useful for chordal and co-comparability graphs
• Algorithmic graph theory and perfect graphs
• Approximating Bandwidth by Mixing Layouts of Interval Graphs
• Cluster deletion on interval graphs and split related graphs
• Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
• Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage
• Connected domination and steiner set on asteroidal triple-free graphs
• Directed subset feedback vertex set is fixed-parameter tractable
• Dominating sets for split and bipartite graphs
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
• Enumerating minimal subset feedback vertex sets
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• Finding Hamiltonian circuits in interval graphs
• Finding the minimum bandwidth of an interval graph
• Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
• Hadwiger number of graphs with small chordality
• In memoriam Walter Kern
• Linear recognition of almost interval graphs
• Maximal Flow Through a Network
• More applications of the d-neighbor equivalence: acyclicity and connectivity constraints
• Multicut Is FPT
• Node multiway cut and subset feedback vertex set on graphs of bounded mim-width
• On asteroidal sets in chordal graphs
• On the computational complexity of vertex integrity and component order connectivity
• On the tractability of optimization problems on \(H\)-graphs
• Parameterized algorithms
• Parameterized algorithms for Steiner tree and dominating set: bounding the leafage by the vertex leafage
• Parameterized graph separation problems
• Polynomial-Time Algorithm for the Leafage of Chordal Graphs
• Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs
• Quick separation in chordal and split graphs
• Reduced clique graphs of chordal graphs
• Representation of a finite graph by a set of intervals on the real line
• Restricted vertex multicut on permutation graphs
• Steiner trees, connected domination and strongly chordal graphs
• The firebreak problem
• 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 vertex leafage of chordal graphs
• Token sliding on split graphs

Cited in

(1)

• Edge multiway cut and node multiway cut are hard for planar subcubic graphs

This page was built for publication: Domination and cut problems on chordal graphs with bounded leafage

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