Packing circuits in matroids期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

Packing circuits in matroids

Authors:

Institution:

(1) Department of Mathematics, Louisiana State University, Baton Rouge, LA 70803, USA;(2) Department of Mathematics, University of Hong Kong, Hong Kong, China

Abstract:

The purpose of this paper is to characterize all matroids M that satisfy the following minimax relation: for any nonnegative integral weight function w defined on E(M),

${\begin{aligned} & {\rm Maximum} \{ k: M\,{\rm has}\,k\,{\rm circuits\,(repetition\,allowed)\,such\,that\,each\,element}\,e\,{\rm of}\,M\\ &\quad\quad\quad\quad\quad {\rm is\,used\,at\,most}\,2w(e)\,{\rm times\,by\,these\,circuits}\}\\ =\,&{\rm Minimum}\left\{\sum\nolimits_{x\in X} w(x): X\,{\rm is\,a\,collection\,of\,elements\,(repetition\,allowed)\,of}\,M \right.\\ &\quad \quad\quad\quad\quad\left.\vphantom{\sum_{x\in X}} {\rm such\,that\,every\,circuit\,in}\,M\,{\rm meets}\,X\,{\rm at\,least\,twice}\right\}. \end{aligned}}$

Our characterization contains a complete solution to a research problem on 2-edge-connected subgraph polyhedra posed by Cornuéjols, Fonlupt, and Naddef in 1985, which was independently solved by Vandenbussche and Nemhauser in Vandenbussche and Nemhauser (J. Comb. Optim. 9:357–379, 2005). W. Zang’s research partially supported by the Research Grants Council of Hong Kong.

Keywords:

Matroid Circuit Polyhedron Total dual integrality Traveling salesman problem

本文献已被 SpringerLink 等数据库收录！

设为首页 | 免责声明 | 关于勤云 | 加入收藏