A network flow approach to a common generalization of Clar and Fries numbers

arXiv2307.03285MaRDI QIDQ6442897FDOQ6442897

Authors: Erika R. Bérczi-Kovács, András Frank 

Publication date: 6 July 2023

Abstract: 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.

This page was built for publication: A network flow approach to a common generalization of Clar and Fries numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6442897)