---
res:
  bibo_abstract:
  - Given a finite set of red and blue points in R^d, the MST-ratio is defined as
    the total length of the Euclidean minimum spanning trees of the red points and
    the blue points, divided by the length of the Euclidean minimum spanning tree
    of their union. The MST-ratio has recently gained attention due to its direct
    interpretation in topological models for studying point sets with applications
    in spatial biology. The maximum MST-ratio of a point set is the maximum MST-ratio
    over all proper colorings of its points by red and blue. We prove that finding
    the maximum MST-ratio of a given point set is NP-hard when the dimension is part
    of the input. Moreover, we present a quadratic-time 3-approximation algorithm
    for this problem. As part of the proof, we show that in any metric space, the
    maximum MST-ratio is smaller than 3. Furthermore, we study the average MST-ratio
    over all colorings of a set of n points. We show that this average is always at
    least n-2/n-1, and for n random points uniformly distributed in a d-dimensional
    unit cube, the average tends to (math formular) in expectation as n approaches
    infinity.@eng
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Afrouz
      foaf_name: Jabal Ameli, Afrouz
      foaf_surname: Jabal Ameli
  - foaf_Person:
      foaf_givenName: Faezeh
      foaf_name: Motiei, Faezeh
      foaf_surname: Motiei
  - foaf_Person:
      foaf_givenName: Morteza
      foaf_name: Saghafian, Morteza
      foaf_surname: Saghafian
      foaf_workInfoHomepage: http://www.librecat.org/personId=f86f7148-b140-11ec-9577-95435b8df824
  bibo_doi: 10.1007/978-981-95-7127-7_26
  bibo_volume: 16444
  dct_date: 2026^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/0302-9743
  - http://id.crossref.org/issn/1611-3349
  - http://id.crossref.org/issn/9789819571260
  dct_language: eng
  dct_publisher: Springer Nature@
  dct_title: 'On the MST-ratio: Theoretical bounds and complexity of finding the maximum@'
...