A competitive algorithm in searching for many edges in a hypergraph
顯示簡易詮釋資料 統計資料| 欄位 | 內容 | 語言 |
|---|---|---|
dc.citation.epage |
571 | en_US |
dc.citation.issue |
4 | en_US |
dc.citation.spage |
566 | en_US |
dc.citation.volume |
155 | en_US |
dc.citation.woscount |
1 | |
dc.contributor.author |
Chen, Ting | en_US |
dc.contributor.author |
Hwang, Frank K. | en_US |
dc.contributor.department |
應用數學系 | zh_TW |
dc.contributor.department |
Department of Applied Mathematics | en_US |
dc.date.accessioned |
2014-12-08T15:14:41Z | |
dc.date.available |
2014-12-08T15:14:41Z | |
dc.date.issued |
2007-02-15 | en_US |
dc.description.abstract |
We give a competitive algorithm to identify all d defective edges in a hypergraph with d unknown. Damaschke did the d = 1 case for 2-graphs, Triesch extended the d = 1 case to r-graphs, and Johann did the general d case for 2-graphs. So ours is the first attempt to solve the searching for defective edges problem in its full generality. Further, all the above three papers assumed d known. We give a competitive algorithm where d is unknown. (c) 2006 Elsevier B.V. All rights reserved. | en_US |
dc.identifier.doi |
10.1016/j.dam.2006.07.008 | en_US |
dc.identifier.issn |
0166-218X | en_US |
dc.identifier.journal |
DISCRETE APPLIED MATHEMATICS | en_US |
dc.identifier.uri |
http://dx.doi.org/10.1016/j.dam.2006.07.008 | en_US |
dc.identifier.uri |
https://ir.lib.nycu.edu.tw/handle/11536/11129 | |
dc.identifier.wosnumber |
WOS:000244827700012 | |
dc.language.iso |
en_US | en_US |
dc.subject |
competitive algorithm | en_US |
dc.subject |
hypergraph | en_US |
dc.subject |
edge-searching problem | en_US |
dc.subject |
group testing | en_US |
dc.subject |
graph searching | en_US |
dc.title |
A competitive algorithm in searching for many edges in a hypergraph | en_US |
dc.type |
Article | en_US |
檔案
- 000244827700012.pdf (142.8 KB, Adobe PDF)
所屬典藏: 期刊論文