Balancing problems in acyclic networks
type: Item
instance of: scholarly article
title: Balancing problems in acyclic networks
zbMATH Open document ID: 0811.90108
DOI: 10.1016/0166-218X(94)90202-X
author: Endre Boros
author: Peter L. Hammer
author: Mark Hartmann
author: Ron Shamir
published in: Discrete Applied Mathematics
publication date: 1994-06-15T00:00:00Z
review text: The authors regard a balancing problem in acyclic networks. Arc lengths are called balanced if any two paths with common endpoints have the same length. The buffer assignment problem arises in a network if the sum of the added amounts is minimal, in such a way that the arc lengths are balanced. The authors give procedures which solve several generalizations of the problem in polynomial time. The network flow theory is used. The authors solve a weighted version of the problem for nonrooted networks and upper bounds of buffers. It is shown that the problem of balancing a network while minimizing the number of arcs with positive buffers is NP-hard.
reviewed by: G.Merkel
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90B10
Mathematics Subject Classification ID: 90C60
Mathematics Subject Classification ID: 68W35
zbMATH DE Number: 590196
zbMATH Keywords: balancing problem in acyclic networks
zbMATH Keywords: buffer assignment
Wikidata QID: Q59560968
MaRDI profile type: Publication
cites work: Cyclic Scheduling via Integer Programs with Circular Ones
cites work: A polynomial algorithm for balancing acyclic data flow graphs
cites work: Q5583694
cites work: Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
cites work: Fibonacci heaps and their uses in improved network optimization algorithms
cites work: The Rectilinear Steiner Tree Problem is $NP$-Complete
cites work: Q3352816
cites work: Finding minimum cost to time ratio cycles with small integral transit times
cites work: Critical-Path Planning and Scheduling: Mathematical Basis
cites work: Q3048571
cites work: Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
cites work: Computing optimal scalings by parametric network algorithms
cites work: Q3707420
cites work: Faster parametric shortest path and minimum‐balance algorithms
cites work: Linear and combinatorial optimization in ordered algebraic structures
DBLP publication ID: journals/dam/BorosHHS94
description: scientific article; zbMATH DE number 590196