Consider a bipartite graph; let’s suppose we draw the origin nodes and the destination nodes arranged in two columns, and the edges as straight-line segments. A noncrossing matching is a subset of edges such that no two of them intersect. Several algorithms for the problem of finding the noncrossing matching of maximum cardinality are proposed. Moreover an extension to weighted graphs is considered.

Efficient labelling algorithms for the maximum noncrossing matching problem / F., Malucelli; T., Ottmann; Pretolani, Daniele. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - STAMPA. - 47 (2):(1993), pp. 175-179. [10.1016/0166-218X(93)90090-B]

Efficient labelling algorithms for the maximum noncrossing matching problem

PRETOLANI, Daniele
1993

Abstract

Consider a bipartite graph; let’s suppose we draw the origin nodes and the destination nodes arranged in two columns, and the edges as straight-line segments. A noncrossing matching is a subset of edges such that no two of them intersect. Several algorithms for the problem of finding the noncrossing matching of maximum cardinality are proposed. Moreover an extension to weighted graphs is considered.
1993
47 (2)
175
179
Efficient labelling algorithms for the maximum noncrossing matching problem / F., Malucelli; T., Ottmann; Pretolani, Daniele. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - STAMPA. - 47 (2):(1993), pp. 175-179. [10.1016/0166-218X(93)90090-B]
F., Malucelli; T., Ottmann; Pretolani, Daniele
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/585407
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 31
  • ???jsp.display-item.citation.isi??? 21
social impact