Optimal Algorithms for Finding the Longest Path with Length and Sum Constraints in a Tree

スポンサーリンク

概要

• 論文の詳細を見る

• Let T be a tree in which every edge is associated with a real number. The sum of a path in T is the sum of the numbers associated with the edges of the path and its length is the number of the edges in it. For two positive integers L1 ≤ L2 and two real numbers S1 ≤ S2, a path is feasible if its length is between L1 and L2 and its sum is between S1 and S2. We address the problem: Given a tree T, and four numbers, L1, L2, S1 and S2, find the longest feasible path of T. We provide an optimal O(nlog n) time algorithm for the problem, where n=|T|.

• 2011-06-01

著者

• Kim Sung

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

• KIM Sung

  School of Computer Science and Engineering, Chung-Ang University

関連論文

• 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

スポンサーリンク