论文标题
一种用于在亚地带图中查找最大诱导匹配的精确算法
An Exact Algorithm for finding Maximum Induced Matching in Subcubic Graphs
论文作者
论文摘要
最大诱导的匹配问题要求找到最大的$ k $，以便给定图形$ g =（v，e）$，我们可以找到一个顶点$ s $ s $ k $的子集，该$ k $的每个顶点$ v $在诱导的图形$ g [s] $中的每个顶点$ v $都完全具有$ 1 $。在本文中，我们设计了一种以$ o（1.2630^n）$时间和多项式空间运行的精确算法，以解决图形最大诱导的匹配问题，在该图中，每个顶点最多都具有3个学位。此方法使用$ O（1.3139^n）$时间。
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.
