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

DOI10.1016/J.DAM.2008.10.018zbMATH Open1201.68075OpenAlexW2032595672MaRDI QIDQ972328FDOQ972328

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

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

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)

Cites Work

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

Cited In (5)

• New Upper Bounds on Continuous Tree Edge-Partition Problem
• Continuous bottleneck tree partitioning problems
• Title not available (Why is that?)
• 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)