hrvatski jezikClear Cookie - decide language by browser settings

The hypermetric cone and polytope on graphs

Dutour Sikirić, Mathieu (2019) The hypermetric cone and polytope on graphs. Chebyshevskii Sbornik, 20 (2). pp. 161-168. ISSN 2226-8383

[img]
Preview
PDF - Published Version - article
Available under License Creative Commons Attribution.

Download (606kB) | Preview

Abstract

The hypermetric cone was defined in DGL92 and was extensively studied by Michel Deza and his collaborators. Another key interest of him was cut and metric polytope which he considered in his last works in the case of graphs. Here we combine both interest by considering the hypermetric on graphs. We define them for any graph and give an algorithm for computing the extreme rays and facets of hypermetric cone on graphs. We compute the hypermetric cone for the first non-trivial case of K7-{; ; e}; ; . We also compute the hypermetric cone in the case of graphs with no K5 minor.

Item Type: Article
Uncontrolled Keywords: hypermetric cone ; graph ; minor
Subjects: NATURAL SCIENCES > Mathematics
Divisions: Division for Marine and Enviromental Research
Depositing User: Mathieu Dutour
Date Deposited: 05 Dec 2019 14:42
URI: http://fulir.irb.hr/id/eprint/5230
DOI: 10.22405/2226-8383-2019-20-2

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year

Contrast
Increase Font
Decrease Font
Dyslexic Font
Accessibility