Domination Reliability. Dohmen, K. & Tittmann, P. *Electron. J. Combin.*, 19:#P15, 2012. Paper abstract bibtex We propose a new network reliability measure for some particular kind of service networks, which we refer to as domination reliability. We relate this new reliability measure to the domination polynomial of a graph and the coverage probability of a hypergraph. We derive explicit and recursive formulae for domination reliability and its associated domination reliability polynomial, deduce an analogue of Whitney's broken circuit theorem, and prove that computing domination reliability is NP-hard.

@article{ Dohmen:2012:DR,
author = {Klaus Dohmen and Peter Tittmann},
title = {Domination Reliability},
journal = {Electron. J. Combin.},
year = {2012},
volume = {19},
pages = {#P15},
url = {http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i1p15},
abstract = {We propose a new network reliability measure for some
particular kind of service networks, which we refer to
as domination reliability. We relate this new
reliability measure to the domination polynomial of a
graph and the coverage probability of a hypergraph. We
derive explicit and recursive formulae for domination
reliability and its associated domination reliability
polynomial, deduce an analogue of Whitney's broken
circuit theorem, and prove that computing domination
reliability is NP-hard.},
keywords = {graph, domination, reliability, polynomial, NP-hard,
inclusion-exclusion, broken circuit}
}

Downloads: 0

{"_id":{"_str":"536dfff04c6bdacb280007ef"},"__v":1,"authorIDs":[],"author_short":["Dohmen, K.","Tittmann, P."],"bibbaseid":"dohmen-tittmann-dominationreliability-2012","bibdata":{"downloads":0,"keyword":["graph","domination","reliability","polynomial","NP-hard","inclusion-exclusion","broken circuit"],"bibbaseid":"dohmen-tittmann-dominationreliability-2012","urls":{"Paper":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i1p15"},"role":"author","year":"2012","volume":"19","url":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i1p15","type":"article","title":"Domination Reliability","pages":"#P15","keywords":"graph, domination, reliability, polynomial, NP-hard, inclusion-exclusion, broken circuit","key":"Dohmen:2012:DR","journal":"Electron. J. Combin.","id":"Dohmen:2012:DR","bibtype":"article","bibtex":"@article{ Dohmen:2012:DR,\n author = {Klaus Dohmen and Peter Tittmann},\n title = {Domination Reliability},\n journal = {Electron. J. Combin.},\n year = {2012},\n volume = {19},\n pages = {#P15},\n url = {http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i1p15},\n abstract = {We propose a new network reliability measure for some\n particular kind of service networks, which we refer to\n as domination reliability. We relate this new\n reliability measure to the domination polynomial of a\n graph and the coverage probability of a hypergraph. We\n derive explicit and recursive formulae for domination\n reliability and its associated domination reliability\n polynomial, deduce an analogue of Whitney's broken\n circuit theorem, and prove that computing domination\n reliability is NP-hard.},\n keywords = {graph, domination, reliability, polynomial, NP-hard,\n inclusion-exclusion, broken circuit}\n}","author_short":["Dohmen, K.","Tittmann, P."],"author":["Dohmen, Klaus","Tittmann, Peter"],"abstract":"We propose a new network reliability measure for some particular kind of service networks, which we refer to as domination reliability. We relate this new reliability measure to the domination polynomial of a graph and the coverage probability of a hypergraph. We derive explicit and recursive formulae for domination reliability and its associated domination reliability polynomial, deduce an analogue of Whitney's broken circuit theorem, and prove that computing domination reliability is NP-hard."},"bibtype":"article","biburl":"https://www.mni.hs-mittweida.de/fileadmin/verzeichnisfreigaben/dohmen/Publikationen/Dohmen.bib","downloads":0,"keywords":["graph","domination","reliability","polynomial","np-hard","inclusion-exclusion","broken circuit"],"search_terms":["domination","reliability","dohmen","tittmann"],"title":"Domination Reliability","year":2012,"dataSources":["QAQCDmtGHsz8zZBdf"]}