The diameter of the acyclic Birkhoff polytope

被引：13
|
作者：
Costa, Liliana [1 ]
da Fonseca, C. M. [2 ]
Martins, Enide Andrade [1 ]
机构：
[1] Univ Aveiro, Dept Math, P-3810193 Aveiro, Portugal
[2] Univ Coimbra, Dept Math, CMUC, P-3001454 Coimbra, Portugal
来源：
LINEAR ALGEBRA AND ITS APPLICATIONS | 2008年 / 428卷 / 07期
关键词：
doubly stochastic matrix; Birkhoff polytope; number of vertices; diameter; graphs; tree;
D O I：
10.1016/j.laa.2007.09.028
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
In this work we give an interpretation of vertices and edges of the acyclic Birkhoff polytope, I-n = Omega(n) (T), where T is a tree with it vertices, in terms of graph theory. We generalize a recent result relatively to the diameter of the graph G(I-n). (c) 2007 Elsevier Inc. All rights reserved.
引用
收藏
页码：1524 / 1537
页数：14
相关论文
共 50 条
  • [1] The diameter of the Birkhoff polytope
    Bouthat, Ludovick
    Mashreghi, Javad
    Morneau-Guerin, Frederic
    SPECIAL MATRICES, 2024, 12 (01):
  • [2] Faces of faces of the acyclic Birkhoff polytope
    L. Costa
    E. A. Martins
    Journal of Mathematical Sciences, 2012, 182 (2) : 144 - 158
  • [3] Face counting on an acyclic Birkhoff polytope
    Costa, Liliana
    da Fonseca, C. M.
    Martins, Enide Andrade
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2009, 430 (04) : 1216 - 1235
  • [4] Four Questions on Birkhoff Polytope
    I. Pak
    Annals of Combinatorics, 2000, 4 (1) : 83 - 90
  • [5] Some subpolytopes of the Birkhoff polytope
    Sá, EM
    ELECTRONIC JOURNAL OF LINEAR ALGEBRA, 2006, 15 : 1 - 7
  • [6] The Ehrhart Polynomial of the Birkhoff Polytope
    Matthias Beck
    Dennis Pixton
    Discrete & Computational Geometry, 2003, 30 : 623 - 637
  • [7] The Ehrhart polynomial of the Birkhoff polytope
    Beck, M
    Pixton, D
    DISCRETE & COMPUTATIONAL GEOMETRY, 2003, 30 (04) : 623 - 637
  • [8] ON THE ACYCLIC SUBGRAPH POLYTOPE
    GROTSCHEL, M
    JUNGER, M
    REINELT, G
    MATHEMATICAL PROGRAMMING, 1985, 33 (01) : 28 - 42
  • [9] The number of faces of the tridiagonal Birkhoff polytope
    Costa L.
    da Fonseca C.M.
    Martins E.A.
    Journal of Mathematical Sciences, 2009, 161 (6) : 867 - 877
  • [10] Faces of faces of the tridiagonal Birkhoff polytope
    Costa, Liliana
    Martins, Enide Andrade
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2010, 432 (06) : 1384 - 1404
12345