| Title | : | Computing Maximum Uniquely Restricted Matchings in Restricted Interval Graph |
| Speaker | : | Swapnil Gupta (IITM) |
| Details | : | Tue, 10 May, 2016 3:00 PM @ BSB 361 |
| Abstract: | : | A matching of graph G is a sub-graph of G such that every edge shares no vertex with any other edge. That is, each vertex in matching M has degree one. The size of a matching is the number of edges in that matching. A matching of a graph G is complete if it contains all of G’s vertices. Sometimes this is also called a perfect matching. We say that a graph G1 is an induced sub-graph of a graph G if G1 is isomorphic to a graph whose vertex set V1 is a subset of the vertex set V of G, and whose edge set E1 consists of all the edges of G with both end vertices in V1. A sub-graph H of G is called induced, if for any two vertices u,v in H, u and v are adjacent in H if and only if they are adjacent in G. A uniquely restricted matching is defined to be a matching M whose matched vertices induces a sub-graph which has only one perfect matching. In graph theory, an interval graph G = (V, E) is the intersection graph of a family of intervals on the real line. It has one vertex v ∈ V for each interval I_i = (a_i , b_i ) in the family, and an edge between every pair of vertices corresponding to intervals that intersect. In this paper, we make progress on the open question of the status of this problem on interval graphs (graphs obtained as the intersection graph of intervals on a line). We give an algorithm to compute maximum cardinality uniquely restricted matchings on certain sub-classes of interval graphs. We consider two sub-classes of interval graphs, the former contained in the latter, and give O(|E|^2 ) time algorithms for both of them. It is to be noted that both sub-classes are incomparable to proper interval graphs (graphs obtained as the intersection graph of intervals in which no interval completely contains another interval), on which the problem can be solved in polynomial time. |
