The maximum weight spanning star forest problem on cactus graphs

DOI10.1142/S1793830915500184zbMath1316.05095OpenAlexW2169948211MaRDI QIDQ5261052

Viet Hung Nguyen

Publication date: 1 July 2015

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s1793830915500184

zbMATH Keywords

dominating setcactus graphsstar forestgenomic sequence alignment

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Dynamic programming (90C39) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (3)

Complexity and approximability of extended spanning star forest problems in general and complete graphs ⋮ On the star forest polytope for trees and cycles ⋮ Weighted Upper Edge Cover: Complexity and Approximability

Cites Work

• On Variants of the Spanning Star Forest Problem
• Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment

This page was built for publication: The maximum weight spanning star forest problem on cactus graphs