Node-balancing by edge-increments

DOI10.1007/978-3-662-48350-3_38zbMATH Open1466.68057arXiv1504.06919OpenAlexW1934654566MaRDI QIDQ3452807FDOQ3452807

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

Publication date: 19 November 2015

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

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.

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

Recommendations

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

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)

Cites Work

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

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)