Frank R. Libsch, Takatoshi Tsujimura
Active Matrix Liquid Crystal Displays Technology and Applications 1997
A matching in a graph is a set of edges no two of which share a common vertex. In this paper we introduce a new, specialized type of matching which we call uniquely restricted matchings, originally motivated by the problem of determining a lower bound on the rank of a matrix having a specified zero/non-zero pattern. A uniquely restricted matching is defined to be a matching M whose saturated vertices induce a subgraph which has only one perfect matching, namely M itself. We introduce the two problems of recognizing a uniquely restricted matching and of finding a maximum uniquely restricted matching in a given graph, and present algorithms and complexity results for certain special classes of graphs. We demonstrate that testing whether a given matching M is uniquely restricted can be done in O(|M||E|) time for an arbitrary graph G = (V, E) and in linear time for cacti, interval graphs, bipartite graphs, split graphs and threshold graphs. The maximum uniquely restricted matching problem is shown to be NP-complete for bipartite graphs, split graphs, and hence for chordal graphs and comparability graphs, but can be solved in linear time for threshold graphs, proper interval graphs, cacti and block graphs.
Frank R. Libsch, Takatoshi Tsujimura
Active Matrix Liquid Crystal Displays Technology and Applications 1997
Da-Ke He, Ashish Jagmohan, et al.
ISIT 2007
Vladimir Yanovski, Israel A. Wagner, et al.
Ann. Math. Artif. Intell.
Kenneth L. Clarkson, K. Georg Hampel, et al.
VTC Spring 2007