{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,2]],"date-time":"2025-07-02T04:10:52Z","timestamp":1751429452297,"version":"3.41.0"},"reference-count":0,"publisher":"SAGE Publications","issue":"3-4","license":[{"start":{"date-parts":[[2000,1,1]],"date-time":"2000-01-01T00:00:00Z","timestamp":946684800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Fundamenta Informaticae"],"published-print":{"date-parts":[[2000,7]]},"abstract":"<jats:p> We consider the problem of constructing reliable comparator networks built from unreliable comparators. In case of a faulty comparator inputs are directly output without comparison. A trivial lower bound of \u03a9(logn + k) on the depth of n-input k-fault tolerant sorting network is well known. We are interested in establishing exact lower bounds on the depth of such networks. To this end we consider fairly simple minimum-finding networks. Our main result is the first nontrivial lower bound on depths of networks computing minimum among n &gt; 2 items in the presence of k &gt; 0 faulty comparators. We prove that the depth of any such network is at least max([logn] + 2k, logn + klog logn\/k+1). We also describe a network whose depth nearly matches the lower bound. <\/jats:p>","DOI":"10.3233\/fi-2000-423402","type":"journal-article","created":{"date-parts":[[2019,12,3]],"date-time":"2019-12-03T03:10:01Z","timestamp":1575342601000},"page":"235-249","source":"Crossref","is-referenced-by-count":1,"title":["Reliable Minimum Finding Comparator Networks"],"prefix":"10.1177","volume":"42","author":[{"given":"Piotr","family":"Denejko","sequence":"first","affiliation":[{"name":"Instytut Informatyki, Uniwersytet Warszawski, Banacha 2, 02-097 Warszawa, Poland. Email: diks@mimuw.edu.pl"}]},{"given":"Krzysztof","family":"Diks","sequence":"additional","affiliation":[{"name":"Instytut Informatyki, Uniwersytet Warszawski, Banacha 2, 02-097 Warszawa, Poland. Email: diks@mimuw.edu.pl"}]},{"given":"Andrzej","family":"Pelc","sequence":"additional","affiliation":[{"name":"D\u00e9partement d'Informatique, Universit\u00e9 du Qu\u00e9bec \u00e0 Hull, Hull, Qu\u00e9bec J8X 3X7, Canada. Email: pelc@uqah.uquebec.ca"}]},{"given":"Marek","family":"Piotr\u00f3w","sequence":"additional","affiliation":[{"name":"Instytut Informatyki, Uniwersytet Wroc\u0142awski, Przesmyckiego 20, 51-151 Wroc\u0142aw, Poland. Email: Marek.Piotrow@ii.uni.wroc.pl"}]}],"member":"179","published-online":{"date-parts":[[2000,1,1]]},"container-title":["Fundamenta Informaticae"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/FI-2000-423402","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/FI-2000-423402","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T10:51:03Z","timestamp":1751367063000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.3233\/FI-2000-423402"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,1,1]]},"references-count":0,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2000,7]]}},"alternative-id":["10.3233\/FI-2000-423402"],"URL":"https:\/\/doi.org\/10.3233\/fi-2000-423402","relation":{},"ISSN":["0169-2968","1875-8681"],"issn-type":[{"type":"print","value":"0169-2968"},{"type":"electronic","value":"1875-8681"}],"subject":[],"published":{"date-parts":[[2000,1,1]]}}}