Parameterized algorithms for Steiner tree and dominating set: bounding the leafage by the vertex leafage

DOI10.1007/978-3-030-96731-4_21MaRDI QIDQ2154102zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 13 July 2022

Full work available at URL https://doi.org/10.1007/978-3-030-96731-4_21

zbMATH Keywords

dominating setchordal graphsSteiner treeundirected path graphsFPT algorithms

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
• Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
• Subexponential-time parameterized algorithm for Steiner tree on planar graphs
• scientific article; zbMATH DE number 2044939
• When diameter matters: parameterized approximation algorithms for bounded diameter minimum Steiner tree problem
• Algorithmic aspects of Steiner convexity and enumeration of Steiner trees
• scientific article; zbMATH DE number 4063109
• Improved Steiner tree algorithms for bounded treewidth
• Improved Steiner tree algorithms for bounded treewidth
• Approximation algorithms for packing element-disjoint Steiner trees on bounded terminal nodes

Cites work

• A recognition algorithm for the intersection graphs of directed paths in directed trees
• A recognition algorithm for the intersection graphs of paths in trees
• Dominating Sets in Chordal Graphs
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• Fourier meets M\"{o}bius: fast subset convolution
• Graph classes with structured neighborhoods and algorithmic applications
• Independent domination in graphs: A survey and recent results
• Intersection graphs of paths in a tree
• Mim-width. III. Graph powers and generalized distance domination problems
• On the tractability of optimization problems on \(H\)-graphs
• Parameterized algorithms
• Polynomial-Time Algorithm for the Leafage of Chordal Graphs
• Revising Johnson's table for the 21st century
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
• Steiner trees, connected domination and strongly chordal graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The Isomorphism Problem For Directed Path Graphs and For Rooted Directed Path Graphs
• The NP-completeness column: an ongoing guide
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The leafage of a chordal graph
• The vertex leafage of chordal graphs

Cited in

(2)

• Parameterized algorithms for Steiner tree and (connected) dominating set on path graphs
• Domination and Cut Problems on Chordal Graphs with Bounded Leafage

This page was built for publication: Parameterized algorithms for Steiner tree and dominating set: bounding the leafage by the vertex leafage

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