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

DOI10.1016/J.DAM.2008.10.018MaRDI QIDQ972328zbMATH OpenOpenAlexFDO

Authors 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

tree partitioningparametric searchsorted matricesratio searchrational search

Mathematics Subject Classification ID

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

Recommendations

• New Upper Bounds on Continuous Tree Edge-Partition Problem
• A tight bound on the min-ratio edge-partitioning problem of a tree
• Continuous bottleneck tree partitioning problems
• On the uniform edge-partition of a tree
• A shifting algorithm for constrained min-max partition on trees

Cites work

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

Cited in

(5)

• New Upper Bounds on Continuous Tree Edge-Partition Problem
• Continuous bottleneck tree partitioning problems
• scientific article; zbMATH DE number 2075844 (Why is no real title available?)
• A tight bound on the min-ratio edge-partitioning problem of a tree
• A linear-time algorithm for finding an edge-partition with max-min ratio at most two

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

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