On finding convex cuts in general, bipartite and plane graphs
On finding convex cuts in general, bipartite and plane graphs
复制标题
关于寻找一般图、二分图和平面图的凸割
DOI：
10.1016/j.tcs.2017.07.026
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
H. Meyerhenke
中科院分区：
文献类型：
--
作者：
R. Glantz;H. Meyerhenke
凸性的一般概念也适用于图G =（V，E）。V的一个子集V c称为凸集，如果所有端点在V c内的最短路都在V c内。G的凸割是V的一个划分（V1，V2），使得V1和V2是凸集（半空间）。一般图的凸割是NP-难的。本文首先利用Djoković关系刻画了连通二部图G ′的凸割，Djoković关系是图的边上的一种自反对称关系，它基于边的端点之间的最短路.特别地，我们证明了G ′的割是凸的当且仅当Djoković关系对它的割集中的任何一对边成立。因此，G ′ ={V ′，E ′}的所有凸割都可以在O（|V ′|| E ′|).然后利用图G的边上的Djoković-Winkler关系θ和另一个关系τ刻画了一般连通图G的凸割.基于这个一般的特征，我们展示了如何在多项式时间内找到G的所有凸割。这里的关键部分是（i）用二分图上的Djoković关系θ ′来描述G的边上的Djoković-Winkler关系，（ii）研究θ ′和τ在表示凸割的平面曲线上的相互作用，（iii）对我们的凸割算法的运行时间进行分析。我们的方法的特点和发现凸割的连通平面图G的动机交替割的概念和条件，后者是凸的。在本文的最后一部分，我们表示为平面曲线的交替切割，并专注于他们的相交模式。如果平面曲线构成伪线的排列，则G是嵌入其对偶中的标度，并且G的任何边都包含在G的凸割的割集中。
The general notion of convexity also applies to a graph G=(V, E). A subset V c of V is called a convex set if all shortest paths with end vertices in V c remain within V c. A convex cut of G is a partition (V 1, V 2) of V such that V 1 and V 2 are convex sets (halfspaces). Finding convex cuts is NP-hard for general graphs. In this paper we first characterize the convex cuts of a connected bipartite graph G′ in terms of the Djoković relation, a reflexive and symmetric relation on the edges of a graph that is based on shortest paths between the edges' end vertices. Specifically, we show that a cut of G′ is convex if and only if the Djoković relation holds for any pair of edges in its cut-set. As a consequence, all convex cuts of G′={V′, E′} can be found in O (| V′|| E′|). We then characterize the convex cuts of a general connected graph G using the Djoković–Winkler relation θ and another relation τ on the edges of G. Based on this general characterization, we show how one can find all convex cuts of G in polynomial time. The key parts here are (i) describing the Djoković–Winkler relation on the edges of G in terms of the Djoković relation θ′ on the bipartite graph obtained from G by subdividing each edge of G into two edges,(ii) studying the interplay of θ′ and τ on plane curves representing convex cuts, and (iii) a running time analysis of our algorithm for finding the convex cuts. Our method for characterizing and finding convex cuts of a connected plane graph G is motivated by the concept of alternating cuts and conditions on the latter to be convex. In the last part of this paper we represent alternating cuts as plane curves and focus on their intersection pattern. If the plane curves form an arrangement of pseudolines, G is scale embedded in its dual, and any edge of G is contained in the cut-set of a convex cut of G.
登录
查看更多内容
DOI：
10.1016/j.jalgor.2004.07.011
发表时间：
2006
期刊：
J. Algorithms
影响因子：
--
作者：
V. Chepoi;F. Dragan;Y. Vaxès
通讯作者：
Y. Vaxès
影响因子：
0.7
作者：
M. C. Dourado;Fábio Protti;D. Rautenbach;J. Szwarcfiter
通讯作者：
J. Szwarcfiter
在立方时间内求平面图的所有凸割
DOI：
10.1007/978-3-642-38233-8_21
发表时间：
2013
期刊：
ArXiv
影响因子：
--
作者：
R. Glantz;Henning Meyerhenke
通讯作者：
Henning Meyerhenke
二分图的凸 p 划分
DOI：
10.1016/j.tcs.2015.11.014
发表时间：
2015
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
L. N. Grippo;M. Matamala;M. Safe;M. Stein
通讯作者：
M. Stein
DOI：
10.1002/jgt.3190160508
发表时间：
1992
期刊：
J. Graph Theory
影响因子：
--
作者：
T. Feder
通讯作者：
T. Feder