.png){kind=icon}
返回
Reconfiguring Multiple Connected Components with Size Multiset Constraints
.png){kind=icon}
PRE
AI
DOI：10.1007/978-981-95-0218-9_6.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
我们提出了一种新的独立集重构（ISR）的泛化：连通分量重构（CCR）。在CCR中，给定一个图G、两个顶子集A和B以及一个正整数多重集M。问题是A和B是否能在某种规则下重构，同时确保每个顶子集诱导的连通分量的大小与多重集M匹配。ISR是CCR的一个特例，其中M仅包含1。我们还提出了新的重构规则：分量跳跃（CJ）和分量滑动（CS），它们将连通分量视为标记。由于CCR泛化了ISR，该问题是PSPACE完全的。与之相反，我们证明了三个正面结果：首先，当G为路径时，CCR-CS和CCR-CJ分别可在线性时间和二次时间内求解。其次，我们证明CCR-CS可在线性时间内求解图是拟阵图的情况。第三，当M仅包含相同元素（即所有连通分量大小相同）时，我们证明若G为弦图，CCR-CJ可在线性时间内求解。第二和第三结果泛化了ISR的已知结果，并展示了重构规则之间的有趣差异。
Keyword:
Combinatorial reconfiguration
Graph algorithm
Connected component
Cograph
Chordal graph
期刊
C
IF:
0
论文数:
24
被引数:
0
.png){kind=icon}
查看更多内容