On some non crossing matching problems
Prof. Federico Malucelli, DEIB Politecnico di Milano
Sala conferenze IMATI-CNR, Pavia - Thursday, May 11, 2017 h.15:00
Abstract. In this presentation we deal with problems depending both on the topology of a bipartite graph and on the geometry of it, defined by its embedding in the plane. The topology of the bipartite graph is fully represented by G = (L∪R,E), where L = {l1,l2,...,lnL} and R = {r1,r2,...,rnR} are two disjoint sets of vertices, and E ⊆ L × R is the set of the m edges, each of which is an ordered pair of vertices. The edge connecting vertex ri to vertex lj will be denoted by the ordered pair (i, j). As for the geometry of the problem, we assume that an embedding of the graph in the plane is given, and precisely: the vertices in L are arranged in a column (on the left), and the vertices in R are arranged in a different parallel column (on the right), in both cases following top-down the total order given by their indices in their own set; the edges are segments connecting the corresponding vertices. Two distinct edges (i,j), (h,k) ∈ E intersect if and only if i < h and j > k. This is to say, two distinct edges intersect if they cross each other in the plane.
A classical problem is to determine the maximum cardinality non crossing matching. We will overview some efficient algorithms for this problem.
We will then tackle the extension to the b-matching case. Consider nR + nL positive integer values b(l1),b(l2),...,b(lnL), b(r1),b(r2),...,b(rnR), A non-crossing b-matching K for G is a subset of edges with the following two properties: i) two non-adjacent edges of K do not cross each other in the plane; and ii) no more than b(v) edges of K are incident on vertex v for all v ∈ L ∪ R.
We will consider the problem of partitioning the edge set of G into the minimum number of non crossing b-matchings. A nice min-max property allows us to devise an exact efficient algorithm. We will also analyze some interesting properties of the Integer Linear Programming formulation of the problem.
This work is the result of a long lasting collaboration with Sara Nicoloso and Daniele Pretolani
References
[1] F. Malucelli and S.Nicoloso (2001), “Optimal partition of a bipartite graph into non-crossing matchings ”, Electronic Notes in Discrete Mathematics 10,187 – 191.
[2] F. Malucelli, T. Ottmann and D. Pretolani, (1993) “Efficient labelling algorithms for the max- imum noncrossing matching problem”, Discrete Applied Mathematics 47(2), 175–179.
Università degli Studi di Pavia -
Via Ferrata, 5 - 27100 Pavia
Tel +39.0382.985600 - Fax +39.0382.985602