A linear-time algorithm for finding an edge-partition with max-min ratio at most two
type: Item
instance of: scholarly article
title: A linear-time algorithm for finding an edge-partition with max-min ratio at most two
zbMATH Open document ID: 1262.05144
author: An-Chiang Chu
author: Bang Ye Wu
author: Kun-Mao Chao
published in: Discrete Applied Mathematics
publication date: 2013-04-25T00:00:00Z
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C22
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 6157656
zbMATH Keywords: partition
zbMATH Keywords: graph partition
zbMATH Keywords: optimization problem
zbMATH Keywords: edge weight
zbMATH Keywords: egde-weighted connected simple graph
zbMATH Keywords: edge-disjoint connected components
zbMATH Keywords: max-min ratio
MaRDI profile type: Publication
full work available at URL: j.dam.2012.11.009
OpenAlex ID: W1987820729
cites work: Shifting algorithms for tree partitioning with general weighting functions
cites work: A Shifting Algorithm for Min-Max Tree Partitioning
cites work: A shifting algorithm for continuous tree partitioning
cites work: New Upper Bounds on Continuous Tree Edge-Partition Problem
cites work: Approximating the Maximally Balanced Connected Partition Problem in graphs
cites work: A tight bound on the min-ratio edge-partitioning problem of a tree
cites work: Q3138951
cites work: Finding kth paths and p-centers by generating and searching good data structures
cites work: Partitioning a Weighted Tree to Subtrees of Almost Uniform Size
cites work: A Linear Tree Partitioning Algorithm
cites work: Improved algorithms for the continuous tree edge-partition problems and a note on ratio and sorted matrices searches
cites work: Max-Min Tree Partitioning
cites work: Efficient implementation of a shifting algorithm
cites work: Spanning Trees and Optimization Problems
cites work: On the uniform edge-partition of a tree
DOI: 10.1016/J.DAM.2012.11.009
description: scientific article; zbMATH DE number 6157656