{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T21:20:34Z","timestamp":1742937634317,"version":"3.40.3"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319411675"},{"type":"electronic","value":"9783319411682"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-41168-2_13","type":"book-chapter","created":{"date-parts":[[2016,7,4]],"date-time":"2016-07-04T01:26:28Z","timestamp":1467595588000},"page":"150-161","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Reconstructing Cactus Graphs from Shortest Path Information"],"prefix":"10.1007","author":[{"given":"Evangelos","family":"Kranakis","sequence":"first","affiliation":[]},{"given":"Danny","family":"Krizanc","sequence":"additional","affiliation":[]},{"given":"Yun","family":"Lu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,7,5]]},"reference":[{"key":"13_CR1","unstructured":"Abrahamsen, M., Bodwin, G., Rotenberg, E., St\u00f6ckel, M.: Graph reconstruction with a betweenness oracle. In: 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), vol. 47, pp. 5:1\u20135:14 (2016)"},{"key":"13_CR2","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1017\/S0963548300000535","volume":"2","author":"M Aigner","year":"1993","unstructured":"Aigner, M., Triesch, E.: Reconstructing a graph from its neighborhood lists. Comb. Probab. Comput. 2, 103\u2013113 (1993)","journal-title":"Comb. Probab. Comput."},{"issue":"1 Second Intern","key":"13_CR3","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1111\/j.1749-6632.1979.tb32774.x","volume":"319","author":"Lowell W. Beineke","year":"1979","unstructured":"Beineke, L., Schmeichel, E.: Degrees and cycles in graph. In: 2nd International Conference on Combinatorial Mathematics, pp. 64\u201370 (1979)","journal-title":"Annals of the New York Academy of Sciences"},{"issue":"2","key":"13_CR4","doi-asserted-by":"publisher","first-page":"199","DOI":"10.7155\/jgaa.00255","volume":"16","author":"B Ben-Moshe","year":"2012","unstructured":"Ben-Moshe, B., Dvir, A., Segal, M., Tamir, A.: Centdian computation in cactus graphs. J. Graph Algorithms Appl. 16(2), 199\u2013224 (2012)","journal-title":"J. Graph Algorithms Appl."},{"key":"13_CR5","first-page":"205","volume":"75","author":"T B\u0131y\u0131ko\u011flu","year":"2005","unstructured":"B\u0131y\u0131ko\u011flu, T.: Degree sequences of Halin graphs, and forcibly cograph-graphic sequences. Ars Combinatoria 75, 205\u2013210 (2005)","journal-title":"Ars Combinatoria"},{"key":"13_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/jgt.3190140102","volume":"14","author":"B Bollobas","year":"1990","unstructured":"Bollobas, B.: Almost every graph has reconstruction number three. J. Graph Theor. 14, 1\u20134 (1990)","journal-title":"J. Graph Theor."},{"issue":"3","key":"13_CR7","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1002\/jgt.20302","volume":"58","author":"P Bose","year":"2008","unstructured":"Bose, P., Dujmovi\u0107, V., Krizanc, D., Langerman, S., Morin, P., Wood, D., Wuhrer, S.: A characterization of the degree sequences of 2-trees. J. Graph Theor. 58(3), 191\u2013209 (2008)","journal-title":"J. Graph Theor."},{"key":"13_CR8","unstructured":"Buneman, P.: The recovery of trees from measures of dissimilarity. In: Mathematics in the Archaeological and Historical Sciences, pp. 387\u2013395. Edinburgh University Press (1971)"},{"key":"13_CR9","first-page":"264","volume":"11","author":"P Erdos","year":"1960","unstructured":"Erdos, P., Gallai, T.: Graphs with prescribed degrees of vertices. Mat. Lapok 11, 264\u2013274 (1960)","journal-title":"Mat. Lapok"},{"key":"13_CR10","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1002\/jgt.20544","volume":"68","author":"F Fomin","year":"2011","unstructured":"Fomin, F., Kratochivil, J., Lokshtanov, D., Mancini, F., Telle, J.A.: On the complexity of reconstructing H-free graphs from their star systems. J. Graph Theor. 68, 113\u2013124 (2011)","journal-title":"J. Graph Theor."},{"issue":"6","key":"13_CR11","doi-asserted-by":"publisher","first-page":"1354","DOI":"10.4153\/CJM-1969-149-3","volume":"21","author":"D Geller","year":"1969","unstructured":"Geller, D., Manvel, B.: Reconstruction of cacti. Can. J. Math. 21(6), 1354\u20131360 (1969)","journal-title":"Can. J. Math."},{"issue":"3","key":"13_CR12","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/0095-8956(74)90066-5","volume":"16","author":"W Giles","year":"1974","unstructured":"Giles, W.: The reconstruction of outerplanar graphs. J. Comb. Theor. Ser. B 16(3), 215\u2013226 (1974)","journal-title":"J. Comb. Theor. Ser. B"},{"key":"13_CR13","unstructured":"Hajnal, A., Sos, V. (eds.): Combinatorics. In: Colloquia Mathematica Societatis Janos Bolya 18, vol. II. North-Holland (1978)"},{"key":"13_CR14","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/BF02579333","volume":"1","author":"P Hammer","year":"1981","unstructured":"Hammer, P., Simeone, B.: The splittance of a graph. Combinatorica 1, 275\u2013284 (1981)","journal-title":"Combinatorica"},{"key":"13_CR15","unstructured":"Harary, F.: On the reconstruction of a graph from a collection of subgraphs. In: Theory of Graphs and its Applications (Proceedings Symposium Smolenice, 1963), pp. 47\u201352 (1964)"},{"key":"13_CR16","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1007\/BFb0066431","volume-title":"Graphs and Combinatorics","author":"F Harary","year":"1974","unstructured":"Harary, F.: A survey of the reconstruction conjecture. In: Bari, R.A., Harary, F. (eds.) Graphs and Combinatorics. Lecture Notes in Mathematics, vol. 406, pp. 18\u201328. Springer, Heidelberg (1974)"},{"key":"13_CR17","doi-asserted-by":"crossref","first-page":"477","DOI":"10.21136\/CPM.1955.108220","volume":"80","author":"V Havel","year":"1955","unstructured":"Havel, V.: Eine Bemerkung \u00fcber die Existenz der endlichen Graphen. Casopis Pest. Mat. 80, 477\u2013480 (1955)","journal-title":"Casopis Pest. Mat."},{"key":"13_CR18","doi-asserted-by":"publisher","first-page":"961","DOI":"10.2140\/pjm.1957.7.961","volume":"7","author":"P Kelly","year":"1957","unstructured":"Kelly, P.: A congruence theorem for trees. Pac. J. Math. 7, 961\u2013968 (1957)","journal-title":"Pac. J. Math."},{"key":"13_CR19","unstructured":"Kranakis, E., Krizanc, D., Urrutia, J.: Implicit routing and shortest path information (Extended Abstract). In: Colloquium on Structural Information and Communication Complexity, pp. 101\u2013112 (1995)"},{"key":"13_CR20","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/0012-365X(81)90271-5","volume":"33","author":"F Lalonde","year":"1981","unstructured":"Lalonde, F.: Le problem d\u2019toiles pour graphes est NP-complet. Discrete Math. 33, 271\u2013280 (1981)","journal-title":"Discrete Math."},{"key":"13_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1007\/11809678_24","volume-title":"Computing and Combinatorics","author":"Z Lotker","year":"2006","unstructured":"Lotker, Z., Majumdar, D., Narayanaswamy, N.S., Weber, I.: Sequences characterizing k-trees. In: Chen, D.Z., Lee, D.T. (eds.) COCOON 2006. LNCS, vol. 4112, pp. 216\u2013225. Springer, Heidelberg (2006)"},{"key":"13_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1007\/978-3-642-39206-1_62","volume-title":"Automata, Languages, and Programming","author":"C Mathieu","year":"2013","unstructured":"Mathieu, C., Zhou, H.: Graph reconstruction via distance oracles. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol. 7965, pp. 733\u2013744. Springer, Heidelberg (2013)"},{"key":"13_CR23","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1016\/S0195-6698(03)00030-1","volume":"24","author":"R Merris","year":"2003","unstructured":"Merris, R.: Split graphs. Eur. J. Comb. 24, 413\u2013430 (2003)","journal-title":"Eur. J. Comb."},{"key":"13_CR24","unstructured":"Nishi, T.: On the number of solutions of a class of nonlinear resistive circuits. In: International Symposium on Circuits and Systems, pp. 766\u2013769. IEEE (1991)"},{"issue":"3","key":"13_CR25","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1089\/cmb.2010.0252","volume":"18","author":"B Paten","year":"2011","unstructured":"Paten, B., Diekhans, M., Earl, D., John, J., Ma, J., Suh, B., Haussler, D.: Cactus graphs for genome comparisons. J. Comput. Biol. 18(3), 469\u2013481 (2011)","journal-title":"J. Comput. Biol."},{"key":"13_CR26","doi-asserted-by":"crossref","unstructured":"Pignolet, Y., Schmid, S., Tredan, G.: Adversarial VNet embeddings: a threat for ISPs? In: INFOCOM, pp. 415\u2013419. IEEE (2013)","DOI":"10.1109\/INFCOM.2013.6566806"},{"key":"13_CR27","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1007\/BFb0092287","volume-title":"Combinatorics and Graph Theory","author":"R Rao","year":"1981","unstructured":"Rao, R.: Degree sequences of cacti. In: Rao, S. (ed.) Combinatorics and Graph Theory. Lecture Notes in Mathematics, vol. 885, pp. 410\u2013416. Springer, Heidelberg (1981)"},{"key":"13_CR28","volume-title":"A Collection of Mathematical Problems","author":"S Ulam","year":"1960","unstructured":"Ulam, S.: A Collection of Mathematical Problems. Wiley, New York (1960)"},{"key":"13_CR29","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1016\/0012-365X(83)90099-7","volume":"47","author":"M Rimscha von","year":"1983","unstructured":"von Rimscha, M.: Reconstructibility and perfect graphs. Discrete Math. 47, 283\u2013291 (1983)","journal-title":"Discrete Math."},{"key":"13_CR30","unstructured":"Zmazek, B., \u017derovnik, J.: Estimating the traffic on weighted cactus networks in linear time. In: Ninth International Conference on Information Visualisation, pp. 536\u2013541. IEEE (2005)"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Aspects in Information and Management"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-41168-2_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,23]],"date-time":"2020-09-23T08:06:24Z","timestamp":1600848384000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-41168-2_13"}},"subtitle":["(Extended Abstract)"],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319411675","9783319411682"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-41168-2_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"5 July 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"AAIM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithmic Applications in Management","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Bergamo","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2016","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 July 2016","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20 July 2016","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"aaim2016","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}