Given a bipartite graph and a prescribed layout of it, we address the problem of partitioning the edge set of the graph into the minimum number of non-crossing matchings, that is subsets of edges no two of which share a common vertex or cross each other in the plane. We discuss some lower and upper bounds on the minimum number of classes of such a partition into non-crossing matchings, and devise an exact almost linear algorithm.
Optimal Partition of a Bipartite Graph with prescribed layout into Non-Crossing Matchings
NICOLOSO Sara
2001
Abstract
Given a bipartite graph and a prescribed layout of it, we address the problem of partitioning the edge set of the graph into the minimum number of non-crossing matchings, that is subsets of edges no two of which share a common vertex or cross each other in the plane. We discuss some lower and upper bounds on the minimum number of classes of such a partition into non-crossing matchings, and devise an exact almost linear algorithm.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
