Generating all the Steiner trees and computing Steiner intervals for a fixed number of terminals

DOI10.1016/J.ENDM.2009.11.053MaRDI QIDQ2840557zbMATH OpenOpenAlexFDO

Authors Mitre C. Dourado, Rodolfo Alves de Oliveira, Fábio Protti

Publication date 19 July 2013

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.endm.2009.11.053

zbMATH Keywords

enumerative combinatoricsSteiner convexitySteiner treestrong Steiner interval

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Algorithmic aspects of Steiner convexity and enumeration of Steiner trees
• Steiner intervals in strongly chordal graphs
• Computing optimal Steiner trees in polynomial space
• Steiner trees with n terminals among n+1 nodes
• Dynamic programming for minimum Steiner trees

Cites work

• A Faster Algorithm for the Steiner Tree Problem
• A search strategy for the elementary cycles of a directed graph
• Database Programming Languages
• Faster Steiner Tree Computation in Polynomial-Space
• Fourier meets M\"{o}bius: fast subset convolution
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• On the Steiner, geodetic and hull numbers of graphs
• Steiner distance and convexity in graphs
• Steiner distance in graphs
• The Steiner number of a graph
• The steiner problem in graphs
• The Steiner tree problem

Cited in

(2)

• Algorithmic aspects of Steiner convexity and enumeration of Steiner trees
• Listing induced Steiner subgraphs as a compact way to discover Steiner trees in graphs

This page was built for publication: Generating all the Steiner trees and computing Steiner intervals for a fixed number of terminals

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