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

DOI10.1016/J.DAM.2012.11.009zbMATH Open1262.05144OpenAlexW1987820729MaRDI QIDQ1949099FDOQ1949099

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

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

Recommendations

• A tight bound on the min-ratio edge-partitioning problem of a tree
• On the uniform edge-partition of a tree
• Graph-Theoretic Concepts in Computer Science
• A linear time algorithm for graph partition problems
• Minimum cost subpartitions in graphs

zbMATH Keywords

graph partitionpartitionoptimization problemedge weightedge-disjoint connected componentsegde-weighted connected simple graphmax-min ratio

Mathematics Subject Classification ID

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

Cites Work

• A Linear Tree Partitioning Algorithm
• Partitioning a Weighted Tree to Subtrees of Almost Uniform Size
• Approximating the Maximally Balanced Connected Partition Problem in graphs
• Title not available (Why is that?)
• Finding kth paths and p-centers by generating and searching good data structures
• Max-Min Tree Partitioning
• Spanning Trees and Optimization Problems
• A Shifting Algorithm for Min-Max Tree Partitioning
• 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
• Shifting algorithms for tree partitioning with general weighting functions
• A tight bound on the min-ratio edge-partitioning problem of a tree
• Improved algorithms for the continuous tree edge-partition problems and a note on ratio and sorted matrices searches

Cited In (5)

• An overview of graph covering and partitioning
• Approximate envy-freeness in graphical cake cutting
• A tight bound on the min-ratio edge-partitioning problem of a tree
• A highly efficient algorithm for maximum cut on Halin graphs
• Title not available (Why is that?)

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

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