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

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

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

• Intersection graphs of paths in a tree
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Parameterized Algorithms
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Independent domination in graphs: A survey and recent results
• The vertex leafage of chordal graphs
• The leafage of a chordal graph
• 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
• Graph classes with structured neighborhoods and algorithmic applications
• 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
• 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
• Revising Johnson's table for the 21st century
• Mim-width. III. Graph powers and generalized distance domination problems
• On the tractability of optimization problems on \(H\)-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

   Recommendations

• Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices 👍 👎
• Title not available (Why is that?) 👍 👎
• Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs 👍 👎
• Title not available (Why is that?) 👍 👎
• When diameter matters: parameterized approximation algorithms for bounded diameter minimum Steiner tree problem 👍 👎
• Algorithmic aspects of Steiner convexity and enumeration of Steiner trees 👍 👎
• Title not available (Why is that?) 👍 👎
• 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 👍 👎

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)