Optimal Sequential Flows
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912883714031616 |
|---|---|
| author | Gimbert, Hugo Mascle, Corto Totzke, Patrick |
| author_facet | Gimbert, Hugo Mascle, Corto Totzke, Patrick |
| contents | We provide a new algebraic technique to solve the sequential flow problem in polynomial space. The task is to maximise the flow through a graph where edge capacities can be changed over time by choosing a sequence of capacity labelings from a given finite set. Our method is based on a novel factorization theorem for finite semigroups that, applied to a suitable flow semigroup, allows to derive small witnesses. This generalises to multiple in/output vertices, as well as regular constraints. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_13806 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Optimal Sequential Flows Gimbert, Hugo Mascle, Corto Totzke, Patrick Optimization and Control Data Structures and Algorithms Formal Languages and Automata Theory We provide a new algebraic technique to solve the sequential flow problem in polynomial space. The task is to maximise the flow through a graph where edge capacities can be changed over time by choosing a sequence of capacity labelings from a given finite set. Our method is based on a novel factorization theorem for finite semigroups that, applied to a suitable flow semigroup, allows to derive small witnesses. This generalises to multiple in/output vertices, as well as regular constraints. |
| title | Optimal Sequential Flows |
| topic | Optimization and Control Data Structures and Algorithms Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2511.13806 |