























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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。