{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,29]],"date-time":"2025-12-29T18:50:35Z","timestamp":1767034235921},"reference-count":25,"publisher":"Elsevier","isbn-type":[{"type":"print","value":"9780128114322"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1016\/b978-0-12-809633-8.20424-x","type":"book-chapter","created":{"date-parts":[[2017,12,20]],"date-time":"2017-12-20T23:51:56Z","timestamp":1513813916000},"page":"940-949","source":"Crossref","is-referenced-by-count":5,"title":["Graph Algorithms"],"prefix":"10.1016","author":[{"given":"Riccardo","family":"Dondi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giancarlo","family":"Mauri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Italo","family":"Zoppis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/B978-0-12-809633-8.20424-X_bib1","doi-asserted-by":"crossref","first-page":"927","DOI":"10.1089\/cmb.2007.0015","article-title":"A novel method for signal transduction network inference from indirect experimental evidence","volume":"14","author":"Albert","year":"2007","journal-title":"Journal of Computational Biology"},{"key":"10.1016\/B978-0-12-809633-8.20424-X_bib2","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/s00453-007-9055-0","article-title":"Inferring (biological) signal transduction networks via transitive reductions of directed graphs","volume":"51","author":"Albert","year":"2008","journal-title":"Algorithmica"},{"key":"10.1016\/B978-0-12-809633-8.20424-X_bib3","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1090\/qam\/102435","article-title":"On a routing problem","volume":"16","author":"Bellman","year":"1958","journal-title":"Quarterly of Applied Mathematics"},{"key":"10.1016\/B978-0-12-809633-8.20424-X_bib4","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1007\/BF02945456","article-title":"The haplotyping problem: An overview of computational models and solutions","volume":"18","author":"Bonizzoni","year":"2003","journal-title":"Journal of Computer Science and Technology"},{"year":"2009","series-title":"Introduction to Algorithms","author":"Cormen","key":"10.1016\/B978-0-12-809633-8.20424-X_bib5"},{"key":"10.1016\/B978-0-12-809633-8.20424-X_bib6","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connexion with graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Nu-Merische Mathematik"},{"key":"10.1016\/B978-0-12-809633-8.20424-X_bib7","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1186\/s13015-017-0096-x","article-title":"Approximating the correction of weighted and unweighted orthology and paralogy relations","volume":"12","author":"Dondi","year":"2017","journal-title":"Algorithms for Molecular Biology"},{"key":"10.1016\/B978-0-12-809633-8.20424-X_bib8","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1145\/367766.368168","article-title":"Algorithm 97: Shortest path","volume":"5","author":"Floyd","year":"1962","journal-title":"Communication of the ACM"},{"key":"10.1016\/B978-0-12-809633-8.20424-X_bib9","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1145\/360680.360691","article-title":"Expected time bounds for selection","volume":"18","author":"Floyd","year":"1975","journal-title":"Communication of the ACM"},{"year":"1962","series-title":"Flows in Networks","author":"Ford","key":"10.1016\/B978-0-12-809633-8.20424-X_bib10"},{"year":"1995","series-title":"Computers and Intractability; A Guide to the Theory of NP-Completeness","author":"Garey","key":"10.1016\/B978-0-12-809633-8.20424-X_bib11"},{"key":"10.1016\/B978-0-12-809633-8.20424-X_bib12","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/S0166-218X(01)00195-0","article-title":"Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP","volume":"117","author":"Gutin","year":"2002","journal-title":"Discrete Applied Mathematics"},{"key":"10.1016\/B978-0-12-809633-8.20424-X_bib13","doi-asserted-by":"crossref","unstructured":"Karp, R.M., 1972. Reducibility among combinatorial problems, In: Proceedings of a symposium on the Complexity of Computer Computations, held March 20\u201322, 1972, at the IBM Thomas J. Watson Research Center, York-town Heights, New York. pp. 85\u2013103.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"10.1016\/B978-0-12-809633-8.20424-X_bib14","doi-asserted-by":"crossref","unstructured":"Kruskal, J.B., 1956. On the shortest spanning subtree of a graph and the traveling salesman problem. In: Proceedings of the American Mathematical Society, p. 7.","DOI":"10.1090\/S0002-9939-1956-0078686-7"},{"key":"10.1016\/B978-0-12-809633-8.20424-X_bib15","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1093\/bib\/3.1.23","article-title":"Algorithmic strategies for the single nucleotide polymorphism haplotype assembly problem","volume":"3","author":"Lippert","year":"2002","journal-title":"Briefings in Bioinformatics"},{"key":"10.1016\/B978-0-12-809633-8.20424-X_bib16","doi-asserted-by":"crossref","unstructured":"Mucha, M., 2013. Lyndon words and short superstrings. In: Khanna, S. (Ed.), Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6\u20138, 2013, SIAM. pp. 958-972. DOI:10.1137\/1.9781611973105.69.","DOI":"10.1137\/1.9781611973105.69"},{"key":"10.1016\/B978-0-12-809633-8.20424-X_bib17","doi-asserted-by":"crossref","unstructured":"Page, R.D.M., 2002. Modified mincut supertrees. In: Guigo, R., Gusfield, D. (Eds.), Proceedings od the Algorithms in Bioinformatics, Second International Workshop, WABI 2002, Rome, Italy, September 17\u201321, 2002, Springer. pp. 537\u2013552. DOI: 10.1007\/3-540-45784-4_41.","DOI":"10.1007\/3-540-45784-4_41"},{"key":"10.1016\/B978-0-12-809633-8.20424-X_bib18","doi-asserted-by":"crossref","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","article-title":"Shortest connection networks and some generalizations","volume":"36","author":"Prim","year":"1957","journal-title":"The Bell Systems Technical Journal"},{"key":"10.1016\/B978-0-12-809633-8.20424-X_bib19","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/S0166-218X(00)00202-X","article-title":"A supertree method for rooted trees","volume":"105","author":"Semple","year":"2000","journal-title":"Discrete Applied Mathematics"},{"key":"10.1016\/B978-0-12-809633-8.20424-X_bib20","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1145\/321105.321107","article-title":"A theorem on boolean matrices","volume":"9","author":"Warshall","year":"1962","journal-title":"Journal of the ACM"},{"key":"10.1016\/B978-0-12-809633-8.20424-X_bib21","first-page":"24","article-title":"Minimum spanning trees for gene expression data clustering","volume":"12","author":"Xu","year":"2001","journal-title":"Genome Informatics"},{"key":"10.1016\/B978-0-12-809633-8.20424-X_fur1","series-title":"Combinatorial Optimization","article-title":"The Traveling Salesman Problem and its Variations","author":"Gutin","year":"2002"},{"year":"2013","series-title":"Algorithm Design","author":"Kleinberg","key":"10.1016\/B978-0-12-809633-8.20424-X_fur2"},{"key":"10.1016\/B978-0-12-809633-8.20424-X_fur3","series-title":"Algorithms and Combinatorics","article-title":"Combinatorial optimization: Polyhedra and efficiency","author":"Schrijver","year":"2002"},{"year":"2008","series-title":"The Algorithm Design Manual","author":"Skiena","key":"10.1016\/B978-0-12-809633-8.20424-X_fur4"}],"container-title":["Encyclopedia of Bioinformatics and Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:B978012809633820424X?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:B978012809633820424X?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,1,22]],"date-time":"2019-01-22T00:50:05Z","timestamp":1548118205000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/B978012809633820424X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9780128114322"],"references-count":25,"URL":"https:\/\/doi.org\/10.1016\/b978-0-12-809633-8.20424-x","relation":{},"subject":[],"published":{"date-parts":[[2019]]}}}