期刊
THEORETICAL COMPUTER SCIENCE
卷 953, 期 -, 页码 -出版社
ELSEVIER
DOI: 10.1016/j.tcs.2023.113796
关键词
Graph algorithms; Parameterized complexity; Branching algorithms
This paper addresses the BICLUSTER EDITING and FLIP CONSENSUS TREE problems and presents algorithms with running times of O*(2.22k) and O(3.24k) respectively, improving upon previous algorithms.
In the BICLUSTER EDITING (resp., FLIP CONSENSUS TREE) problem the input is a bipartite graph G = (V1, V2, E) and an integer k, and the goal is to decide whether there is a set F c V1 X V2 such that the graph (V1, V2, EAF) does not contain an induced path on four vertices (resp., an induced path on five vertices whose endpoints are in V2). In this paper we give algorithms for BICLUSTER EDITING and FLIP CONSENSUS TREE whose running times are O *(2.22k) and O(3.24k), respectively. This improves over the O *(2.636k)-time algorithm for BICLUSTER EDITING of Tsur [IPL 2021] and the O*(3.68k)-time algorithm for FLIP CONSENSUS TREE of Komusiewicz and Uhlmann [Algorithmica 2014].(c) 2023 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据