We study the depth of decision trees for diagnosis of constant 0 and 1 faults in read-once contact networks over finite bases containing only indecomposable networks. For each basis, we obtain a linear upper bound on the minimum depth of decision trees depending on the number of edges in the networks. For bases containing networks with at most 10 edges we find coefficients for linear bounds which are close to sharp. © 2014 Elsevier B.V. All rights reserved.
|Original language||English (US)|
|Number of pages||13|
|Journal||Discrete Applied Mathematics|
|State||Published - Mar 2015|
Bibliographical noteKAUST Repository Item: Exported on 2020-10-01
Acknowledgements: Research reported in this publication was supported by the King Abdullah University of Science and Technology (KAUST). The authors wish to express their gratitude to anonymous reviewers for useful comments and suggestions.
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics