Minimum Degree Orderings
Minimum Degree Orderings
复制标题
DOI：
10.1007/s00453-008-9239-2
复制
发表时间：
2007-12
期刊：
影响因子：
1.1
通讯作者：
H. Nagamochi
中科院分区：
文献类型：
--
作者：
H. Nagamochi
众所周知，给定一个边权重图，顶点的最大邻接排序(MA排序)可以找到一对特殊的顶点，称为关联对，而图中的最小割可以通过重复收缩一个悬挂对来找到，从而产生最快、最简单的最小割算法之一。在本文中，我们提出了另一种顶点排序，称为最小度排序(MD排序)，作为分析图结构的一个新的基本工具。我们证明了MD序找到了不同类型的特殊顶点对，称为aflat对，实际上可以在重复删除具有最小次数的顶点后得到最后两个顶点。通过收缩平坦对，我们不仅可以找到一个图的最小割，而且可以找到给定图的所有极子集。这些结果可以推广到求对称子模集函数的极值子集的问题。
It is known that, given an edge-weighted graph, a maximum adjacency ordering (MA ordering) of vertices can find a special pair of vertices, called apendent pair, and that a minimum cut in a graph can be found by repeatedly contracting a pendent pair, yielding one of the fastest and simplest minimum cut algorithms. In this paper, we provide another ordering of vertices, called a minimum degree ordering (MD ordering) as a new fundamental tool to analyze the structure of graphs. We prove that an MD ordering finds a different type of special pair of vertices, called aflat pair, which actually can be obtained as the last two vertices after repeatedly removing a vertex with the minimum degree. By contracting flat pairs, we can find not only a minimum cut but also all extreme subsets of a given graph. These results can be extended to the problem of finding extreme subsets in symmetric submodular set functions.