.png){kind=icon}
.png){kind=icon}
返回
The maximum beer flow problem*
.png){kind=icon}
PRE
AI
DOI：10.1016/j.tcs.2026.115768.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
设G = (V, E, B)是一个具有顶点集V、边集E和特殊顶点子集B c V的图，B被称为啤酒商店。从u到v的啤酒路径是一条从u开始、在v结束且至少访问一个啤酒商店的路径。啤酒路径的概念最近被引入和研究，重点在于寻找图中的最短啤酒路径。在本工作中，我们探索了这一概念的天然扩展，即我们所谓的啤酒流。我们证明，最大啤酒流问题可以通过线性规划来表述，从而可以在多项式时间内求解。然而，当每条边上的流量被限制为整数时，该问题突然变得NP难，即使在非常简单的情况下也是如此。这一结果与传统最大流问题形成鲜明对比，在后者的整数流不会使问题复杂化。
Keyword:
Beer path
Beer flow
NP-Hardness
Approximation