Article ID Journal Published Year Pages File Type
10328482 Discrete Applied Mathematics 2005 5 Pages PDF
Abstract
Recently, Johann gave an algorithm to find all d defective edges in a graph assuming d=|D| is known. We give an algorithm with d unknown which requires at most d(⌈log2|E|⌉+4)+1 tests. The information-theoretic bound, knowing d, is about dlog2(|E|/d). For d fixed, our algorithm is competitive with coefficient 1.
Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
A competitive algorithm to find all defective edges in a graph
Authors
,