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

DOI10.1016/j.dam.2012.11.009zbMath1262.05144OpenAlexW1987820729MaRDI QIDQ1949099

Kun-Mao Chao, An-Chiang Chu, Bang Ye Wu

Publication date: 25 April 2013

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

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

zbMATH Keywords

partitionoptimization problemmax-min ratiograph partitionedge weightedge-disjoint connected componentsegde-weighted connected simple graph

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)

Related Items (1)

An overview of graph covering and partitioning

Cites Work

• A tight bound on the min-ratio edge-partitioning problem of a tree
• Approximating the Maximally Balanced Connected Partition Problem in graphs
• Improved algorithms for the continuous tree edge-partition problems and a note on ratio and sorted matrices searches
• Efficient implementation of a shifting algorithm
• A shifting algorithm for continuous tree partitioning
• On the uniform edge-partition of a tree
• New Upper Bounds on Continuous Tree Edge-Partition Problem
• Partitioning a Weighted Tree to Subtrees of Almost Uniform Size
• Shifting algorithms for tree partitioning with general weighting functions
• Max-Min Tree Partitioning
• A Shifting Algorithm for Min-Max Tree Partitioning
• A Linear Tree Partitioning Algorithm
• Spanning Trees and Optimization Problems
• Finding kth paths and p-centers by generating and searching good data structures
• Unnamed Item

This page was built for publication: A linear-time algorithm for finding an edge-partition with max-min ratio at most two