论文标题
Győri-Lovász定理的高效构造几乎是弦图
Efficient Constructions for the Győri-Lovász Theorem on Almost Chordal Graphs
论文作者
论文摘要
在1970年代，Győri和Lovász表明，对于$ k $连接的$ n $ - vertex图，给定的一组终端顶点$ t_1，\ dots，\ dots，t_k $和自然数量$ n_1，\ dots，\ dots，n_k $ n_k $ n_k $ \ sum_ $ \ sum_ = 1 = 1} $ s $ s $ s $ \ dots，s_k $满足$ t_i \ in s_i $和$ | s_i | = n_i $存在。但是，到目前为止，多项式算法实际计算此类分区仅以$ k \ leq 4 $而闻名。这促使我们采用一种新的方法并将此问题限制为特定的图形类，而不是限制$ k $的值。更确切地说，我们考虑了$ k $连接的和弦图和与它们相关的更广泛的图形。首先，我们给出了一种$ o（n^2）$运行时间的算法，该算法准确地解决了该问题，第二个算法是一种带有$ o（n^4）$运行时间的算法，该算法最多偏离所需的顶点的顶点。
In the 1970s, Győri and Lovász showed that for a $k$-connected $n$-vertex graph, a given set of terminal vertices $t_1, \dots, t_k$ and natural numbers $n_1, \dots, n_k$ satisfying $\sum_{i=1}^{k} n_i = n$, a connected vertex partition $S_1, \dots, S_k$ satisfying $t_i \in S_i$ and $|S_i| = n_i$ exists. However, polynomial algorithms to actually compute such partitions are known so far only for $k \leq 4$. This motivates us to take a new approach and constrain this problem to particular graph classes instead of restricting the values of $k$. More precisely, we consider $k$-connected chordal graphs and a broader class of graphs related to them. For the first, we give an algorithm with $O(n^2)$ running time that solves the problem exactly, and for the second, an algorithm with $O(n^4)$ running time that deviates on at most one vertex from the given required vertex partition sizes.
