10 citations · 23 across the 10 of their papers we have counts for
12 papers
A network flow approach to a common generalization of Clar and Fries numbers
Erika Bérczi-Kovács, András Frank
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…
Decreasing Minimization on Base-Polyhedra: Relation Between Discrete and Continuous Cases
András Frank, Kazuo Murota
This paper is concerned with the relationship between the discrete and the continuous decreasing minimization problem on base-polyhedra. The continuous version (under the name of l…
Fair Integral Submodular Flows
András Frank, Kazuo Murota
Integer-valued elements of an integral submodular flow polyhedron are investigated which are decreasingly minimal (dec-min) in the sense that their largest component is as smal…
Decreasing Minimization on M-convex Sets: Algorithms and Applications
András Frank, Kazuo Murota
This paper is concerned with algorithms and applications of decreasing minimization on an M-convex set, which is the set of integral elements of an integral base-polyhedron. Based…
A Discrete Convex Min-Max Formula for Box-TDI Polyhedra
András Frank, Kazuo Murota
A min-max formula is proved for the minimum of an integer-valued separable discrete convex function where the minimum is taken over the set of integral elements of a box total dual…
Fair Integral Network Flows
András Frank, Kazuo Murota
A strongly polynomial algorithm is developed for finding an integer-valued feasible -flow of given flow-amount which is decreasingly minimal on a specified subset of edges…
Discrete Decreasing Minimization, Part II: Views from Discrete Convex Analysis
András Frank, Kazuo Murota
We continue to consider the discrete decreasing minimization problem on an integral base-polyhedron treated in Part I. The problem is to find a lexicographically minimal integral v…
Discrete Decreasing Minimization, Part I: Base-polyhedra with Applications in Network Optimization
András Frank, Kazuo Murota
Borradaile et al. (2017) investigated orientations of an undirected graph in which the sequence of in-degrees of the nodes is lexicographically minimal, which we call decreasingly…
Supermodularity in Unweighted Graph Optimization II: Matroidal Term Rank Augmentation
Kristóf Bérczi, András Frank
Ryser's max term rank formula with graph theoretic terminology is equivalent to a characterization of degree sequences of simple bipartite graphs with matching number at least $\el…
Supermodularity in Unweighted Graph Opitimization III: Highly-connected Digraphs
Kristóf Bérczi, András Frank
By generalizing a recent result of Hong, Liu, and Lai on characterizing the degree-sequences of simple strongly connected directed graphs, a characterization is provided for degree…
Supermodularity in Unweighted Graph Optimization I: Branchings and Matchings
Kristóf Bérczi, András Frank
The main result of the paper is motivated by the following two, apparently unrelated graph optimization problems: (A) as an extension of Edmonds' disjoint branchings theorem, chara…
Sink-Stable Sets of Digraphs
Dóra Erdős, András Frank, Krisztián Kun
We introduce the notion of sink-stable sets of a digraph and prove a min-max formula for the maximum cardinality of the union of k sink-stable sets. The results imply a recent min-…