Node-balancing by edge-increments

DOI10.1007/978-3-662-48350-3_38MaRDI QIDQ3452807zbMATH OpenOpenAlexFDO

Authors Friedrich Eisenbrand, Shay Moran, Rom Pinchasi, Martin Skutella

Publication date 19 November 2015

Published in Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.06919

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) Signed and weighted graphs (05C22) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Suppose you are given a graph $G=(V,E)$ with a weight assignment $w:VightarrowmathbbZ$ and that your objective is to modify $w$ using legal steps such that all vertices will have the same weight, where in each legal step you are allowed to choose an edge and increment the weights of its end points by $1$. In this paper we study several variants of this problem for graphs and hypergraphs. On the combinatorial side we show connections with fundamental results from matching theory such as Hall's Theorem and Tutte's Theorem. On the algorithmic side we study the computational complexity of associated decision problems. Our main results are a characterization of the graphs for which any initial assignment can be balanced by edge-increments and a strongly polynomial-time algorithm that computes a balancing sequence of increments if one exists.

Recommendations

• On integer balancing of directed graphs
• Balanced problems on graphs with categorization of edges
• Stabilizing weighted graphs
• Stabilizing weighted graphs

Cites work

• scientific article; zbMATH DE number 432790 (Why is no real title available?)
• scientific article; zbMATH DE number 3637616 (Why is no real title available?)
• A polynomial algorithm for b-matchings: An alternative approach
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Combinatorial Optimization with Rational Objective Functions
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Faster scaling algorithms for general graph matching problems
• Finding minimum-cost circulations by canceling negative cycles
• Maximum matching and a polyhedron with 0,1-vertices
• Paths, Trees, and Flowers
• Regularisable graphs I
• The Factors of Graphs

Cited in

(2)

• Balanced binary mappings on graphs
• On integer balancing of directed graphs

This page was built for publication: Node-balancing by edge-increments

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