Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2307.03285 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of 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.