Counting integer flows in networks

被引：29

作者：

Baldoni-Silva, W

De Loera, JA

Vergne, M

机构：

[1] Univ Roma Tor Vergata, Dipartimento Matemat, I-00133 Rome, Italy

[2] Univ Calif Davis, Dept Math, Davis, CA 95616 USA

[3] Ecole Polytech, Ctr Math, F-91128 Palaiseau, France

来源：

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS | 2004年 / 4卷 / 03期

关键词：

integral flows; flow polytopes; lattice points; rational function manipulation; hyperplane arrangements; residues; transportation problems; kostant partition function; chambers;

D O I：

10.1007/s10208-003-0088-8

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This paper discusses analytic algorithms and software for the enumeration of all integer flows inside a network. Concrete applications abound in graph theory, representation theory, and statistics. Our methods are based on the study of rational functions with poles on arrangements of hyperplanes; they surpass traditional exhaustive enumeration and can even yield formulas when the input data contains some parameters. We also discuss the calculation of chambers in detail because it is a necessary subroutine.

引用

页码：277 / 314

页数：38

共 31 条

[1]

ALEKSEYEVSKAYA TV, 1988, SOV MATH DOKL, V36, P589

[2]

[Anonymous], 1996, Combinatorics and commutative algebra

[3]

[Anonymous], 1996, Doc. Math

[4]

[Anonymous], 1992, Oriented Matroids

[5]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[6]

BALDONISILVA W, 2001, UNPUB RESIDUES FORMU

[7]

Barvinok A., 1999, Math. Sci. Res. Inst. Publ., V38, P91

[8]

BECK M, IN PRESS DISCRETE CO

[9] DUALITY AND MINORS OF SECONDARY POLYHEDRA [J].

BILLERA, LJ ;

GELFAND, IM ;

STURMFELS, B .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1993, 57 (02) :258-268

[10] Residue formulae, vector partition functions and lattice points in rational polytopes [J].

Brion, M ;

Vergne, M .

JOURNAL OF THE AMERICAN MATHEMATICAL SOCIETY, 1997, 10 (04) :797-833

← 1 2 3 4 →