Faster deterministic algorithm for Co-Path Set

被引：0
作者：
Tsur, Dekel [1 ]
机构：
[1] Ben Gurion Univ Negev, Dept Comp Sci, Beer Sheva, Israel
来源：
INFORMATION PROCESSING LETTERS | 2023年 / 180卷
关键词：
Graph algorithms; Parameterized complexity; Branching algorithms; RADIATION HYBRID MAP;
D O I：
10.1016/j.ipl.2022.106335
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
In the CO-PATH SET problem, the input is a graph G and an integer k, and the goal is to decide whether there is a set of at most k edges whose removal from G results in a graph in which every connected component is a path. In this paper we give a deterministic O*(2k)-time algorithm for CO-PATH SET.(c) 2022 Elsevier B.V. All rights reserved.
引用
收藏
页数：3
相关论文
共 50 条
12345