{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,23]],"date-time":"2026-02-23T20:49:14Z","timestamp":1771879754003,"version":"3.50.1"},"reference-count":10,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":8259,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1984,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Let <jats:italic>G<\/jats:italic>(<jats:italic>V, E<\/jats:italic>) be an undirected graph which describes the structure of a communication network. During the maintenance period every line must be tested in each of the two possible directions. A line is tested by assigning one of its endpoints to be a transmitter, the other to be a receiver, and sending a message from the transmitter to the receiver through the line. We define several different models for communication networks, all subject to the two following axioms: a vertex cannot act as a transmitter and as a receiver simultaneously and a vertex cannot receive through two lines simultaneously. In each of the models, two problems arise: What is the maximum number of lines one can test simultaneously? and What is the minimum number of phases necessary for testing the entire network?, where, by \u201cphase\u201d we mean a period in which some tests are conducted simultaneously. We show that in most models, including the \u201cnatural\u201d model of radio communication, both problems are NP\u2010hard. In some models the problems can be solved by reducing them to either a maximum matching problem or an edge coloring problem for which polynomial algorithms are known. One model remains for which the complexity of the minimization problem is unknown.<\/jats:p>","DOI":"10.1002\/net.3230140102","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T17:17:43Z","timestamp":1178903863000},"page":"1-24","source":"Crossref","is-referenced-by-count":65,"title":["On the np\u2010completeness of certain network testing problems"],"prefix":"10.1002","volume":"14","author":[{"given":"S.","family":"Even","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"O.","family":"Goldreich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Moran","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P.","family":"Tong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"The Design and Analysis of Computer Algorithms","author":"Aho A. V.","year":"1974"},{"key":"e_1_2_1_3_2","volume-title":"Computers and Intractability\u2010A Guide to the Theory of NP\u2010Completeness","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_1_4_2","unstructured":"S.Even Graph Algorithms Computer Science (1979)."},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"e_1_2_1_6_2","doi-asserted-by":"crossref","unstructured":"S.MichaliandV. V.Vazirani An(O\/surdy|V|.|E|)algorithm for finding maximum matching in general graphs. 21st Annual Symposium on the Foundations of Computer Science IEEE Computer Society 1980.","DOI":"10.1109\/SFCS.1980.12"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/0211009"},{"key":"e_1_2_1_8_2","first-page":"25","article-title":"On an estimate of the chromatic class of a p\u2010graph (in Russian)","volume":"3","author":"Vizing V. G.","year":"1964","journal-title":"Diskret. Analiz."},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/0210055"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90077-1"},{"key":"e_1_2_1_11_2","unstructured":"S.Even O.Goldreich andP.Tong On the NP\u2010completeness of certain network testing problems. TR#230 Dept. of Computer Science Technion."}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230140102","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230140102","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,19]],"date-time":"2023-10-19T23:19:09Z","timestamp":1697757549000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230140102"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1984,3]]},"references-count":10,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1984,3]]}},"alternative-id":["10.1002\/net.3230140102"],"URL":"https:\/\/doi.org\/10.1002\/net.3230140102","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1984,3]]}}}