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 noncrossing 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 noncrossing matchings, and devise an exact almost linear algorithm.
Optimal Partition of a Bipartite Graph with Prescribed Layout into NonCrossing 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 noncrossing 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 noncrossing 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.
