單位圓盤意指半徑為1的圓形，由n個落在歐幾里得平面中的單位圓盤所組成的交錯圖，我們稱之為單位圓盤圖。每個圓盤的圓心視為圖形中的端點，若是任兩個圓盤間有所交疊，則代表圓盤的端點間有邊相鄰。在本論文中，我們探討在單位圓盤圖中的最大導出配對問題，在圖G中的最大導出配對問題是找出最大的邊個數，這些邊皆無法被圖G當中的邊所連接。我們利用了分支化約的技巧來分析圖形，在分支化約演算法與轉換本問題成為最大獨立集合問題的策略下，我們提出了一個時間複雜度為O^* (〖1.4228〗^n)與多項式空間複雜度的演算法。

A unit disk is a circle with radius 1. A unit disk graph is an intersection graph consisting of n unit disks in the Euclidean plane. The center of each disk be the vertex of graph; if two disks intersect, the two corresponding vertices are connected by an edge.
In this paper, we study the MAXIMUM INDUCED MATCHING problem in unit disk graphs. A MAXIMUM INDUCED MATCHING problem in a graph G is to fi nd the maximum cardinality of edges where none of two are connected by another edge in G. We apply the technique of branch-and-reduce to analyze the problem. With the combination of branch-and-reduce algorithm and the transformation of the problem
into the MAXIMUM INDEPENDENT SET problem, we give an algorithm that runs in time O*(1.4228n) and polynomial space.

[1] H. Balakrishnan, C. L. Barrett, V. A. Kumar, M. V. Marathe, & S. Thite (2004).
The distance-2 matching problem and its relationship to the MAC-layer capacity
of ad hoc wireless networks. IEEE Journal on Selected Areas in Communications,
22(6), 1069-1079.
[2] B. Balasundaram, & S. Butenko (2006). Graph domination, coloring and cliques
in telecommunications. In Handbook of Optimization in Telecommunications (pp.
865-890). Springer, Boston, MA.
[3] H. Breu, & D. G. Kirkpatrick (1998). Unit disk graph recognition is NP-hard.
Computational Geometry, 9(1-2), 3-24.
[4] K. Cameron (1989). Induced matchings. Discrete Applied Mathematics, 24(1-3),
97-102.
[5] M. S. Chang, L. J. Hung, & C. A. Miau (2013). An O (1:4786n)-Time Algorithm
for the Maximum Induced Matching Problem. In Advances in Intelligent Systems
and Applications-Volume 1 (pp. 49-58). Springer, Berlin, Heidelberg.
[6] M. S. Chang, L. H. Chen, & L. J. Hung (2015). Moderately exponential time
algorithms for the maximum induced matching problem. Optimization Letters,
9(5), 981-998.
[7] B. N. Clark, C. J. Colbourn, & D. S. Johnson (1991). Unit disk graphs. In Annals
of Discrete Mathematics (Vol. 48, pp. 165-177). Elsevier.
[8] F. V. Fomin, & P. Kaski (2013). Exact exponential algorithms. Communications
of the ACM, 56(3), 80-88.
[9] M. R. Garey, & D. S. Johnson, (1979). Computers and intractability: A guide to
the theory of npcompleteness (series of books in the mathematical sciences), ed.
Computers and Intractability, 340.
[10] M. C. Golumbic, & M. Lewenstein (2000). New results on induced matchings.
Discrete Applied Mathematics, 101(1-3), 157-165.
[11] S. Gupta, V. Raman, & S. Saurabh (2006, December). Fast exponential algorithms
for maximum r-regular induced subgraph problems. In International Conference
on Foundations of Software Technology and Theoretical Computer Science (pp.
139-151). Springer, Berlin, Heidelberg.
[12] W. K. Hale (1980). Frequency assignment: Theory and applications. Proceedings
of the IEEE, 68(12), 1497-1514.
[13] C. W. Ko, & F. B. Shepherd (2003). Bipartite domination and simultaneous ma-
troid covers. SIAM Journal on Discrete Mathematics, 16(4), 517-523.
[14] D. Kobler, & U. Rotics (2003). Finding maximum induced matchings in subclasses
of claw-free and P5-free graphs, and in graphs with matching and induced matching
of equal maximum size. Algorithmica, 37(4), 327-346.
[15] C. M. Krishnamurthy, & R. Sritharan, (2012). Maximum induced matching prob-
lem on hhd-free graphs. Discrete Applied Mathematics, 160(3), 224-230.
[16] V. V. Lozin (2002). On maximum induced matchings in bipartite graphs. Infor-
mation Processing Letters, 81(1), 7-11.
[17] M. V. Marathe, H. Breu, H. B. Hunt, S. S. Ravi, & D. J. Rosenkrantz (1995).
Simple heuristics for unit disk graphs. Networks, 25(2), 59-68.
[18] L. J. Stockmeyer, & V. V. Vazirani (1982). NP-completeness of some generaliza-
tions of the maximum matching problem. Information Processing Letters, 15(1),
14-19.
[19] M. Xiao, & H. Nagamochi (2017). Exact algorithms for maximum independent
set. Information and Computation, 255, 126-146.
[20] M. Xiao, & H. Tan (2017). Exact Algorithms for Maximum Induced Matching.
Information and Computation, 256, 196-211.
[21] M. Zito, (2000). Linear time maximum induced matching algorithm for trees.
Nord. J. Comput., 7(1), 58.