Group testing in bipartite graphs
顯示簡易詮釋資料 統計資料| 欄位 | 內容 | 語言 |
|---|---|---|
dc.citation.epage |
73 | en_US |
dc.citation.issue |
1 | en_US |
dc.citation.spage |
67 | en_US |
dc.citation.volume |
6 | en_US |
dc.citation.woscount |
0 | |
dc.contributor.author |
Juan, ST | en_US |
dc.contributor.author |
Chang, GJ | en_US |
dc.contributor.department |
應用數學系 | zh_TW |
dc.contributor.department |
Department of Applied Mathematics | en_US |
dc.date.accessioned |
2014-12-08T15:42:46Z | |
dc.date.available |
2014-12-08T15:42:46Z | |
dc.date.issued |
2002-03-01 | en_US |
dc.description.abstract |
This paper investigates the group testing problem in graphs as follows. Given a graph G = (V, E), determine the minimum number t(G) such that t(G) tests are sufficient to identify an unknown edge e with each test specifies a subset X subset of or equal to V and answers whether the unknown edge e is in G[X] or not. Damaschke proved that [log(2) e(G)] less than or equal to t(G) less than or equal to [log(2) e(G)] + 1 for any graph G, where e(G) is the number of edges of G. While there are infinitely many complete graphs that attain the upper bound, it was conjectured by Chang and Hwang that the lower bound is attained by all bipartite graphs. This paper verifies the conjecture for bipartite graphs G with e(G) less than or equal to 2(4) or 2(k-1) < e(G) less than or equal to 2(k-1) + 2(k-3) + 2(k-6) + 19(.)2(k-7/2) -1 for k greater than or equal to 5. | en_US |
dc.identifier.issn |
1027-5487 | en_US |
dc.identifier.journal |
TAIWANESE JOURNAL OF MATHEMATICS | en_US |
dc.identifier.uri |
https://ir.lib.nycu.edu.tw/handle/11536/28989 | |
dc.identifier.wosnumber |
WOS:000178772800004 | |
dc.language.iso |
en_US | en_US |
dc.subject |
group testing | en_US |
dc.subject |
algorithm | en_US |
dc.subject |
complete graph | en_US |
dc.subject |
bipartite graph | en_US |
dc.subject |
induced subgraph | en_US |
dc.title |
Group testing in bipartite graphs | en_US |
dc.type |
Article | en_US |
檔案
本條目沒有附加檔案。
所屬典藏: 期刊論文