A network flow approach to a common generalization of Clar and Fries numbers
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914831481700352 |
|---|---|
| author | Bérczi-Kovács, Erika Frank, András |
| author_facet | Bérczi-Kovács, Erika Frank, András |
| contents | Clar number and Fries number are two thoroughly investigated parameters of plane graphs emerging from mathematical chemistry to measure stability of organic molecules. We consider first a common generalization of these two concepts for bipartite plane graphs, and then extend it to a framework on general (not necessarily planar) directed graphs. The corresponding optimization problem can be transformed into a maximum weight feasible tension problem which is the linear programming dual of a minimum cost network flow (or circulation) problem. Therefore the approach gives rise to a min-max theorem and to a strongly polynomial algorithm that relies exclusively on standard network flow subroutines. In particular, we give the first network flow based algorithm for an optimal Fries structure and its variants. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_03285 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A network flow approach to a common generalization of Clar and Fries numbers Bérczi-Kovács, Erika Frank, András Combinatorics Clar number and Fries number are two thoroughly investigated parameters of plane graphs emerging from mathematical chemistry to measure stability of organic molecules. We consider first a common generalization of these two concepts for bipartite plane graphs, and then extend it to a framework on general (not necessarily planar) directed graphs. The corresponding optimization problem can be transformed into a maximum weight feasible tension problem which is the linear programming dual of a minimum cost network flow (or circulation) problem. Therefore the approach gives rise to a min-max theorem and to a strongly polynomial algorithm that relies exclusively on standard network flow subroutines. In particular, we give the first network flow based algorithm for an optimal Fries structure and its variants. |
| title | A network flow approach to a common generalization of Clar and Fries numbers |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2307.03285 |