A competitive algorithm to find all defective edges in a graph

檔案

日期

2005-06-15

作者

類型

期刊名稱

DISCRETE APPLIED MATHEMATICS

卷期與頁次

第 148 卷第 3 期,頁 273–277

ISSN

0166-218X

語言

英文

摘要

Consider a graph G (V, E) where a subset D E E is called the set of defective edges. The problem is to identify D with a small number of edge tests, where an edge test takes an arbitrary subset S and asks whether the subgraph G(S) induced by S intersects D (contains a defective edge). Recently, Johann gave an algorithm to find all d defective edges in a graph assuming d D I is known. We give an algorithm with d unknown which requires at most d([log(2) vertical bar E vertical bar] + 4) + 1 tests. The information-theoretic bound, knowing d, is about d log(2) (vertical bar E vertical bar/d). For d fixed, our algorithm is competitive with coefficient 1. (c) 2005 Elsevier B.V. All rights reserved.

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料

引用此條目

Hwang, F. (2005). A competitive algorithm to find all defective edges in a graph. DISCRETE APPLIED MATHEMATICS, 148(3), 273–277. https://doi.org/10.1016/j.dam.2005.02.010

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/13581