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

DOI10.1007/978-3-030-96731-4_21OpenAlexW4225918198MaRDI QIDQ2154102

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)

Cites Work

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

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