A strongly polynomial time algorithm for the maximum supply rate problem on trees

DOI10.1016/j.tcs.2019.05.014zbMath1436.68261OpenAlexW2944949267WikidataQ127839294 ScholiaQ127839294MaRDI QIDQ5919326

Koki Takayama, Yusuke Kobayashi

Publication date: 16 January 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2019.05.014

zbMATH Keywords

dynamic programmingstrongly polynomial-time algorithmmaximum supply rate problem

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Transportation, logistics and supply chain management (90B06) Deterministic network models in operations research (90B10) Dynamic programming (90C39) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• A heuristic method for solving the problem of partitioning graphs with supply and demand
• Partitioning graphs of supply and demand
• Approximability of partitioning graphs with supply and demand
• Parametric power supply networks
• Spanning Distribution Trees of Graphs
• PARTITIONING TREES OF SUPPLY AND DEMAND
• Parametric Network Flows

This page was built for publication: A strongly polynomial time algorithm for the maximum supply rate problem on trees