Exact exponential-time algorithms for finding bicliques

被引:8
作者
Binkele-Raible, Daniel [2 ]
Fernau, Henning [2 ]
Gaspers, Serge [3 ]
Liedloff, Mathieu [1 ]
机构
[1] Univ Orleans, LIFO, F-45067 Orleans 2, France
[2] Univ Trier, FB Abt Informat 4, D-54286 Trier, Germany
[3] Vienna Univ Technol, Inst Informat Syst, A-1040 Vienna, Austria
关键词
Graph algorithms; Exact exponential-time algorithms; NP-hard problem; Complete bipartite subgraphs; BIPARTITE; CLIQUE;
D O I
10.1016/j.ipl.2010.10.020
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
Due to a large number of applications, bicliques of graphs have been widely considered in the literature. This paper focuses on non-induced bicliques. Given a graph G = (V. E) on n vertices, a pair (X. Y), with X, Y subset of V, X boolean AND Y = mt set, is a non-induced biclique if {x, y} is an element of E for any x is an element of X and y is an element of Y. The NP-complete problem of finding a non-induced (k(1), k(2))-biclique asks to decide whether G contains a non-induced biclique (X. Y) such that vertical bar X vertical bar = k(1) and vertical bar Y vertical bar = k(2). In this paper, we design a polynomial-space O(1.6914(n))-time algorithm for this problem. It is based on an algorithm for bipartite graphs that runs in time O(1.30052(n)). In deriving this algorithm, we also exhibit a relation to the spare allocation problem known from memory chip fabrication. As a byproduct, we show that the constraint bipartite vertex cover problem can be solved in time O(1.30052(n)). (C) 2010 Elsevier B.V. All rights reserved.
引用
收藏
页码:64 / 67
页数:4
相关论文
共 50 条
[41]   Benchmark Problems for Exhaustive Exact Maximum Clique Search Algorithms [J].
Szabo, Sandor ;
Zavalnij, Bogdan .
INFORMATICA-JOURNAL OF COMPUTING AND INFORMATICS, 2019, 43 (02) :177-186
[42]   Dominating set based exact algorithms for 3-coloring [J].
Narayanaswamy, N. S. ;
Subramanian, C. R. .
INFORMATION PROCESSING LETTERS, 2011, 111 (06) :251-255
[43]   New Exact and Approximation Algorithms for the Star Packing Problem in Undirected Graphs [J].
Babenko, Maxim ;
Gusakov, Alexey .
28TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2011), 2011, 9 :519-530
[44]   ALGORITHMS FOR FINDING THE LARGEST SUBTREE WHOSE COPIES COVER ALL THE LEAVES [J].
AKUTSU, T ;
KOBAYASHI, S ;
HORI, K ;
OHSUGA, S .
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 1993, E76D (06) :707-710
[45]   Local search algorithms for finding the Hamiltonian completion number of line graphs [J].
Detti, Paolo ;
Meloni, Carlo ;
Pranzo, Marco .
ANNALS OF OPERATIONS RESEARCH, 2007, 156 (01) :5-24
[46]   Complexity and Algorithms for Finding a Perfect Phylogeny from Mixed Tumor Samples [J].
Hujdurovic, Ademir ;
Kacar, Ursa ;
Milanic, Martin ;
Ries, Bernard ;
Tomescu, Alexandru I. .
IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS, 2018, 15 (01) :96-108
[47]   Local search algorithms for finding the Hamiltonian completion number of line graphs [J].
Paolo Detti ;
Carlo Meloni ;
Marco Pranzo .
Annals of Operations Research, 2007, 156 :5-24
[48]   Exact Algorithms for Maximum Weighted Independent Set on Sparse Graphs (Extended Abstract) [J].
Huang, Sen ;
Xiao, Mingyu ;
Chen, Xiaoyu .
COMPUTING AND COMBINATORICS (COCOON 2021), 2021, 13025 :617-628
[49]   Hardness results, approximation and exact algorithms for liar's domination problem in graphs [J].
Panda, B. S. ;
Paul, S. ;
Pradhan, D. .
THEORETICAL COMPUTER SCIENCE, 2015, 573 :26-42
[50]   Fully Dynamic Exact Edge Connectivity in Sublinear Time [J].
Goranci, Gramoz ;
Henzinger, Monika ;
Nanongkai, Danupon ;
Saranurak, Thatchaphol ;
Thorup, Mikkel ;
Wulff-Nilsen, Christian .
PROCEEDINGS OF THE 2023 ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, SODA, 2023, :70-86