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

DOI10.1016/J.DAM.2012.11.009MaRDI QIDQ1949099zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(5)

• An overview of graph covering and partitioning
• A tight bound on the min-ratio edge-partitioning problem of a tree
• Approximate envy-freeness in graphical cake cutting
• scientific article; zbMATH DE number 3983202 (Why is no real title available?)
• A highly efficient algorithm for maximum cut on Halin graphs

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)