In this paper we deal with the problem of partitioning the edge set of a bipartite graph G=(L?R,E) with prescribed layout into the minimum number of non-crossing b-matchings. Some bounds and properties are discussed and an exact O(|E|loglogmin{|L|,|R|}) is presented for its solution.
Optimal Partition of a Bipartite Graph with prescribed layout into Non-Crossing b-Matchings
NICOLOSO Sara
2005
Abstract
In this paper we deal with the problem of partitioning the edge set of a bipartite graph G=(L?R,E) with prescribed layout into the minimum number of non-crossing b-matchings. Some bounds and properties are discussed and an exact O(|E|loglogmin{|L|,|R|}) is presented for its solution.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.
