Optimal Algorithms for Finding Density-Constrained Longest and Heaviest Paths in a Tree

スポンサーリンク

概要

• 論文の詳細を見る

• Let T be a tree with n nodes, in which each edge is associated with a length and a weight. The density-constrained longest (heaviest) path problem is to find a path of T with maximum path length (weight) whose path density is bounded by an upper bound and a lower bound. The path density is the path weight divided by the path length. We show that both problems can be solved in optimal O(n log n) time.<br/>

• The Institute of Electronics, Information and Communication Engineersの論文
• 2010-11-01

著者

• Kim Sung

  School Of Computer Sci. And Engineering Chung-ang Univ.

関連論文

• Alteration of Acetaminophen Metabolism by Sulfate and Steroids in Primary Monolayer Hepatocyte Cultures of Rats and Mice
• Forward Link Performance of Combined Soft and Hard Handoff in Multimedia CDMA Systems
• Pt and RuO_2 Bottom Electrode Effects on Pb(Zr,Ti)O_3 Memory Capacitors
• Optimum Modeling of 3-D Circular Braided Composites
• Characteristics of intermixed InGaAs/InGaAsP Multi-Quantum-Well Structure
• Intermixing Characteristics of Strained-InGaAs/InGaAsP Multiple Quantum Well Structure Using Impurity-Free Vacancy Diffusion
• Study of Prominence Detection Based on Various Phone-Specific Features
• Optimal Online and Offline Algorithms for Finding Longest and Shortest Subsequences with Length and Sum Constraints
• Optimal Algorithms for Finding the Longest Path with Length and Sum Constraints in a Tree
• Optimal Algorithms for Finding Density-Constrained Longest and Heaviest Paths in a Tree

スポンサーリンク