Diagnosis of constant faults in read-once contact networks over finite bases

Monther I. Busbait; Igor Chikalov; Shahid Hussain; Mikhail Moshkov

doi:10.1016/j.dam.2014.10.034

Diagnosis of constant faults in read-once contact networks over finite bases

Monther I. Busbait, Igor Chikalov, Shahid Hussain, Mikhail Moshkov

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

Abstract

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)
Pages (from-to)	76-88
Number of pages	13
Journal	Discrete Applied Mathematics
Volume	184
DOIs	https://doi.org/10.1016/j.dam.2014.10.034
State	Published - Mar 2015

Bibliographical note

KAUST 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

Access to Document

10.1016/j.dam.2014.10.034

Cite this

@article{e6a834d451684714a9166cc65e6b1228,

title = "Diagnosis of constant faults in read-once contact networks over finite bases",

abstract = "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. {\textcopyright} 2014 Elsevier B.V. All rights reserved.",

author = "Busbait, {Monther I.} and Igor Chikalov and Shahid Hussain and Mikhail Moshkov",

note = "KAUST 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.",

year = "2015",

month = mar,

doi = "10.1016/j.dam.2014.10.034",

language = "English (US)",

volume = "184",

pages = "76--88",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

}

TY - JOUR

T1 - Diagnosis of constant faults in read-once contact networks over finite bases

AU - Busbait, Monther I.

AU - Chikalov, Igor

AU - Hussain, Shahid

AU - Moshkov, Mikhail

N1 - KAUST 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.

PY - 2015/3

Y1 - 2015/3

N2 - 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.

AB - 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.

UR - http://hdl.handle.net/10754/564091

UR - https://linkinghub.elsevier.com/retrieve/pii/S0166218X1400479X

UR - http://www.scopus.com/inward/record.url?scp=84930599229&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2014.10.034

DO - 10.1016/j.dam.2014.10.034

M3 - Article

SN - 0166-218X

VL - 184

SP - 76

EP - 88

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

Diagnosis of constant faults in read-once contact networks over finite bases

Abstract

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this