Water transport on infinite graphs
Häggström, Olle and Hirscher, Timo LU
(2019)
In Random Structures and Algorithms
54(3).
p.515-527
- Abstract
If the nodes of a graph are considered to be identical barrels – featuring different water levels – and the edges to be (locked) water-filled pipes in between the barrels, consider the optimization problem of how much the water level in a fixed barrel can be raised with no pumps available, that is, by opening and closing the locks in an elaborate succession. This model is related to an opinion formation process, the so-called Deffuant model. We consider the initial water profile to be given by i.i.d. unif(0,1) random variables, investigate the supremum of achievable water levels at a given node – or to be more precise, the support of its distribution – and ask in which settings it becomes degenerate, that is, reduces to a single value.... (More)
If the nodes of a graph are considered to be identical barrels – featuring different water levels – and the edges to be (locked) water-filled pipes in between the barrels, consider the optimization problem of how much the water level in a fixed barrel can be raised with no pumps available, that is, by opening and closing the locks in an elaborate succession. This model is related to an opinion formation process, the so-called Deffuant model. We consider the initial water profile to be given by i.i.d. unif(0,1) random variables, investigate the supremum of achievable water levels at a given node – or to be more precise, the support of its distribution – and ask in which settings it becomes degenerate, that is, reduces to a single value. This turns out to be the case for all infinite connected quasi-transitive graphs, with exactly one exception: the two-sided infinite path.
(Less)
- author
- Häggström, Olle
and Hirscher, Timo
LU
- publishing date
- 2019-05
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- Deffuant model, graph algorithms, infinite path, optimization, water transport
- in
- Random Structures and Algorithms
- volume
- 54
- issue
- 3
- pages
- 13 pages
- publisher
- John Wiley & Sons Inc.
- external identifiers
-
- scopus:85053379834
- ISSN
- 1042-9832
- DOI
- 10.1002/rsa.20801
- language
- English
- LU publication?
- no
- additional info
- Publisher Copyright: © 2018 Wiley Periodicals, Inc.
- id
- 2c83e7aa-ffde-4017-8428-115c3cd46c53
- date added to LUP
- 2023-12-14 13:21:53
- date last changed
- 2023-12-14 15:42:21
@article{2c83e7aa-ffde-4017-8428-115c3cd46c53,
abstract = {{<p>If the nodes of a graph are considered to be identical barrels – featuring different water levels – and the edges to be (locked) water-filled pipes in between the barrels, consider the optimization problem of how much the water level in a fixed barrel can be raised with no pumps available, that is, by opening and closing the locks in an elaborate succession. This model is related to an opinion formation process, the so-called Deffuant model. We consider the initial water profile to be given by i.i.d. unif(0,1) random variables, investigate the supremum of achievable water levels at a given node – or to be more precise, the support of its distribution – and ask in which settings it becomes degenerate, that is, reduces to a single value. This turns out to be the case for all infinite connected quasi-transitive graphs, with exactly one exception: the two-sided infinite path.</p>}},
author = {{Häggström, Olle and Hirscher, Timo}},
issn = {{1042-9832}},
keywords = {{Deffuant model; graph algorithms; infinite path; optimization; water transport}},
language = {{eng}},
number = {{3}},
pages = {{515--527}},
publisher = {{John Wiley & Sons Inc.}},
series = {{Random Structures and Algorithms}},
title = {{Water transport on infinite graphs}},
url = {{http://dx.doi.org/10.1002/rsa.20801}},
doi = {{10.1002/rsa.20801}},
volume = {{54}},
year = {{2019}},
}