Full metadata record
DC FieldValueLanguage
dc.contributor.authorJuan, STen_US
dc.contributor.authorChang, GJen_US
dc.date.accessioned2014-12-08T15:42:46Z-
dc.date.available2014-12-08T15:42:46Z-
dc.date.issued2002-03-01en_US
dc.identifier.issn1027-5487en_US
dc.identifier.urihttp://hdl.handle.net/11536/28989-
dc.description.abstractThis 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.language.isoen_USen_US
dc.subjectgroup testingen_US
dc.subjectalgorithmen_US
dc.subjectcomplete graphen_US
dc.subjectbipartite graphen_US
dc.subjectinduced subgraphen_US
dc.titleGroup testing in bipartite graphsen_US
dc.typeArticleen_US
dc.identifier.journalTAIWANESE JOURNAL OF MATHEMATICSen_US
dc.citation.volume6en_US
dc.citation.issue1en_US
dc.citation.spage67en_US
dc.citation.epage73en_US
dc.contributor.department應用數學系zh_TW
dc.contributor.departmentDepartment of Applied Mathematicsen_US
dc.identifier.wosnumberWOS:000178772800004-
dc.citation.woscount0-
Appears in Collections:Articles