Improved algorithms for the continuous tree edge-partition problems and a note on ratio and sorted matrices searches

DOI10.1016/j.dam.2008.10.018zbMath1201.68075OpenAlexW2032595672MaRDI QIDQ972328

Jyh-Jye Lin, Chi-Yuan Chan, Biing-Feng Wang

Publication date: 25 May 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2008.10.018

zbMATH Keywords

parametric searchtree partitioningsorted matricesratio searchrational search

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

A linear-time algorithm for finding an edge-partition with max-min ratio at most two

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal search for rationals
• The complexity of selection and ranking in X+Y and matrices with sorted columns
• Rational search
• Efficient search for rationals
• Time bounds for selection
• Most uniform path partitioning and its use in image processing
• Continuous bottleneck tree partitioning problems
• A shifting algorithm for continuous tree partitioning
• Generalized Selection and Ranking: Sorted Matrices
• Shifting algorithms for tree partitioning with general weighting functions
• New Results on the Complexity of p-Centre Problems
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Combinatorial Optimization with Rational Objective Functions
• Max-Min Tree Partitioning
• A Shifting Algorithm for Min-Max Tree Partitioning
• Slowing down sorting networks to obtain faster sorting algorithms
• Fair dissections of spiders, worms, and caterpillars

This page was built for publication: Improved algorithms for the continuous tree edge-partition problems and a note on ratio and sorted matrices searches