The maximum weight spanning star forest problem on cactus graphs

DOI10.1142/S1793830915500184zbMATH Open1316.05095OpenAlexW2169948211MaRDI QIDQ5261052FDOQ5261052

Authors: 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

Recommendations

• On the star forest polytope for trees and cycles
• Improved Approximation Algorithms for the Spanning Star Forest Problem
• Improved approximation algorithms for the spanning star forest problem
• Approximating the spanning \(k\)-tree forest problem
• Extended spanning star forest problems

zbMATH Keywords

dominating setcactus graphsstar forestgenomic sequence alignment

Mathematics Subject Classification ID

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

Cites Work

• Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment
• On variants of the spanning star forest problem

Cited In (5)

• Spanning cactus of a graph: Existence, extension, optimization, and approximation
• Weighted upper edge cover: complexity and approximability
• Extended spanning star forest problems
• Complexity and approximability of extended spanning star forest problems in general and complete graphs
• On the star forest polytope for trees and cycles

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

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