Parameterized algorithms for Steiner tree and (connected) dominating set on path graphs
From MaRDI portal
Recommendations
- Steiner trees, connected domination and strongly chordal graphs
- Parameterized dominating set problem in chordal graphs: Complexity and lower bound
- Doubly chordal graphs, steiner trees, and connected domination
- Parameterized Domination in Circle Graphs
- Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs
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
- A survey of selected recent results on total domination in graphs
- Bibliography on domination in graphs and some basic definitions of domination parameters
- Characterizations of strongly chordal graphs
- Characterizing path graphs by forbidden induced subgraphs
- Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage
- Dominating Sets in Chordal Graphs
- Domination, independent domination, and duality in strongly chordal graphs
- Dually Chordal Graphs
- Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
- Graph classes with structured neighborhoods and algorithmic applications
- scientific article; zbMATH DE number 854567 (Why is no real title available?)
- 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 models of directed path graphs non rooted directed path graphs
- Parameterized algorithms
- Parameterized algorithms for Steiner tree and dominating set: bounding the leafage by the vertex leafage
- Polynomial-Time Algorithm for the Leafage of Chordal Graphs
- Revising Johnson's table for the 21st century
- Rooted directed path graphs are leaf powers
- 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 forbidden subgraph characterization of directed vertex graphs
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- The Isomorphism Problem For Directed Path Graphs and For Rooted Directed Path Graphs
- The leafage of a chordal graph
- The NP-completeness column: an ongoing guide
- The vertex leafage of chordal graphs
This page was built for publication: Parameterized algorithms for Steiner tree and (connected) dominating set on path graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6599055)
