{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T14:40:06Z","timestamp":1777646406895,"version":"3.51.4"},"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,2]],"date-time":"2019-12-02T22:10:01Z","timestamp":1575324601000},"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"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Krzysztof","family":"Diks","sequence":"additional","affiliation":[{"name":"Instytut Informatyki, Uniwersytet Warszawski, Banacha 2, 02-097 Warszawa, Poland. Email: diks@mimuw.edu.pl"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"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"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"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"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"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":[[2026,4,29]],"date-time":"2026-04-29T06:35:09Z","timestamp":1777444509000},"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":[{"value":"0169-2968","type":"print"},{"value":"1875-8681","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000,1,1]]}}}