{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,21]],"date-time":"2023-10-21T11:43:29Z","timestamp":1697888609527},"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":7894,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1985,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A special class of reducible digraphs is characterized, those whose transitive reduction of the associated <jats:italic>dag<\/jats:italic> is a directed rooted tree. Polynomial time algorithms are described for the problems of recognition, isomorphism and finding minimum equivalent digraphs of this class. An approximative algorithm is also given for the general case of this last problem. The size of the approximation is always less than twice the exact solution. In addition, isomorphism of depth first search is solved as a special case of isomorphism of this class.<\/jats:p>","DOI":"10.1002\/net.3230150106","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T19:19:12Z","timestamp":1178911152000},"page":"49-57","source":"Crossref","is-referenced-by-count":4,"title":["On digraphs with a rooted tree structure"],"prefix":"10.1002","volume":"15","author":[{"given":"Jayme L.","family":"Szwarcfiter","sequence":"first","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":"Problems Polynomially Equivalent to Graph Isomorphism","author":"Booth K. S.","year":"1979"},{"key":"e_1_2_1_4_2","volume-title":"Programming Languages and their Compilers: Preliminary Notes","author":"Cocke J.","year":"1970"},{"key":"e_1_2_1_5_2","volume-title":"Computers and Intractability: A Guide to the Theory of NP\u2010Completeness","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/0201014"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/321832.321835"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_13"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(73)90030-6"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/0203021"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80049-8"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230150106","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230150106","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,20]],"date-time":"2023-10-20T15:45:03Z","timestamp":1697816703000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230150106"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,3]]},"references-count":10,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1985,3]]}},"alternative-id":["10.1002\/net.3230150106"],"URL":"https:\/\/doi.org\/10.1002\/net.3230150106","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,3]]}}}