Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Water transport on finite graphs

Vilkas, Timo LU orcid (2025) p.1-28
Abstract
Consider a simple finite graph and its nodes to represent identical water barrels (containing different amounts of water) on a level plane. Each edge corresponds to a (locked, water-filled) pipe connecting two barrels below the plane. We fix one node v and consider the optimization problem relating to the maximum value to which the level in v can be raised without pumps, i.e. by opening/closing pipes in a suitable order. This fairly natural optimization problem originated from the analysis of an opinion formation process and proved to be not only sufficiently intricate in order to be of independent interest, but also difficult from an algorithmic point of view.
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Working paper/Preprint
publication status
published
subject
keywords
Water transport, graph algorithms, optimization, complexity, greedy lattice animal
pages
28 pages
publisher
arXiv.org
DOI
10.48550/arXiv.2501.16911
language
English
LU publication?
yes
id
d3f8daf5-28b4-46d1-aaaf-d6566e3d2e4e
date added to LUP
2025-03-10 10:17:21
date last changed
2025-04-04 14:10:25
@misc{d3f8daf5-28b4-46d1-aaaf-d6566e3d2e4e,
  abstract     = {{Consider a simple finite graph and its nodes to represent identical water barrels (containing different amounts of water) on a level plane. Each edge corresponds to a (locked, water-filled) pipe connecting two barrels below the plane. We fix one node v and consider the optimization problem relating to the maximum value to which the level in v can be raised without pumps, i.e. by opening/closing pipes in a suitable order. This fairly natural optimization problem originated from the analysis of an opinion formation process and proved to be not only sufficiently intricate in order to be of independent interest, but also difficult from an algorithmic point of view.}},
  author       = {{Vilkas, Timo}},
  keywords     = {{Water transport; graph algorithms; optimization; complexity; greedy lattice animal}},
  language     = {{eng}},
  month        = {{01}},
  note         = {{Preprint}},
  pages        = {{1--28}},
  publisher    = {{arXiv.org}},
  title        = {{Water transport on finite graphs}},
  url          = {{http://dx.doi.org/10.48550/arXiv.2501.16911}},
  doi          = {{10.48550/arXiv.2501.16911}},
  year         = {{2025}},
}