Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/8358
Title: Identifying the most connected vertices in hidden bipartite graphs using group testing
Authors: Wang, J
Lo, E 
Yiu, ML 
Keywords: Bioinformatics
Bipartite graph
graphs and networks
Image edge detection
Probes
Proteins
Query processing
Switches
Testing
Issue Date: 2013
Publisher: Institute of Electrical and Electronics Engineers
Source: IEEE transactions on knowledge and data engineering, 2013, v. 25, no. 10, 6298889, p. 2245-2256 How to cite?
Journal: IEEE transactions on knowledge and data engineering 
Abstract: A graph is called hidden if the edges are not explicitly given and edge probe tests are required to detect the presence of edges. This paper studies the (k) most connected vertices ((k)MCV) problem on hidden bipartite graphs, which has applications in spatial databases, graph databases, and bioinformatics. There is a prior work on the (k)MCV problem, which is based on the " 2-vertex testing" model, i.e., an edge probe test can only reveal the existence of an edge between two individual vertices. We study the (k)MCV problem, in the context of a more general edge probe test model called " group testing. " A group test can reveal whether there exists some edge between a vertex and a group of vertices. If group testing is used properly, a single invocation of a group test can reveal as much information as multiple invocations of 2-vertex tests. We discuss the cases and applications where group testing could be used, and present an algorithm, namely, GMCV, that adaptively leverages group testing to solve the (k)MCV problem.
URI: http://hdl.handle.net/10397/8358
ISSN: 1041-4347
EISSN: 1558-2191
DOI: 10.1109/TKDE.2012.178
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

3
Last Week
0
Last month
0
Citations as of Nov 8, 2017

WEB OF SCIENCETM
Citations

2
Last Week
0
Last month
0
Citations as of Nov 15, 2017

Page view(s)

41
Last Week
3
Last month
Checked on Nov 19, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.