The Maximum Induced Matching problem asks to find the maximum $k$ such that, given a graph $G=(V,E)$, can we find a subset of vertices $S$ of size $k$ for which every vertices $v$ in the induced graph $G[S]$ has exactly degree $1$. In this paper, we design an exact algorithm running in $O(1.2630^n)$ time and polynomial space to solve the Maximum Induced Matching problem for graphs where each vertex has degree at most 3. Prior work solved the problem by finding the Maximum Independent Set using polynomial space in the line graph $L(G^2)$; this method uses $O(1.3139^n)$ time.
翻译：最大调整匹配问题要求找到最高值为k$, 以便根据一个图形 $G= (V, E) $, 我们能找到一个大小为 $k$ 的脊椎子子集, 其中引导图形 $G[S] $ $ $ $v$ 的每个脊椎都有精确的度值为$1美元。 在本文中, 我们设计了一个精确的算法, 以$O( 1. 2630 n) 的时间和多元空间 来解决每个脊椎最多具有程度的图形 最大值匹配问题 。 3 先前的工作是通过在线性图 $L( G) $2 中找到最大独立设置 来解决这个问题 ; 这种方法使用 $O( 1. 13139 n) 时间 。
相关内容
微信扫码咨询专知VIP会员