The Weighted Maximum-Mean Subtree and Other Bicriterion Subtree Problems

DOI10.1007/11785293_37MaRDI QIDQ5757882zbMATH OpenOpenAlexFDO

Authors Josiah Carlson, David Eppstein

Publication date 7 September 2007

Published in Algorithm Theory – SWAT 2006 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11785293_37

Mathematics Subject Classification ID

Trees (05C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Programming involving graphs or networks (90C35)

Recommendations

• Optimizing constrained subtrees of trees
• A shifting algorithm for constrained min-max partition on trees
• Algorithms and Computation
• Enumeration of subtrees of trees
• FPTASs for trimming weighted trees

Cited in

(9)

• Optimizing constrained subtrees of trees
• FPTASs for trimming weighted trees
• Approximating a class of combinatorial problems with rational objective function
• Choosing Subsets with Maximum Weighted Average
• Exact and Approximation Algorithms for the Expanding Search Problem
• Balancing profits and costs on trees
• A stronger lower bound on parametric minimum spanning trees
• A stronger lower bound on parametric minimum spanning trees
• A linear time algorithm for finding an optimal degree-bounded subtree of an edge-weighted tree

This page was built for publication: The Weighted Maximum-Mean Subtree and Other Bicriterion Subtree Problems

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