{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:14:31Z","timestamp":1725549271153},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540278733"},{"type":"electronic","value":"9783540318606"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11527954_6","type":"book-chapter","created":{"date-parts":[[2010,3,1]],"date-time":"2010-03-01T16:51:11Z","timestamp":1267462271000},"page":"49-62","source":"Crossref","is-referenced-by-count":10,"title":["Cuts and Disjoint Paths in the Valley-Free Path Model of Internet BGP Routing"],"prefix":"10.1007","author":[{"given":"Thomas","family":"Erlebach","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Hall","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alessandro","family":"Panconesi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Danica","family":"Vukadinovi\u0107","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"6_CR1","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"A. Ahuja","year":"1993","unstructured":"Ahuja, A., Magnanti, T., Orlin, J.: Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Englewood Cliffs (1993)"},{"key":"6_CR2","volume-title":"Complexity and Approximation. Combinatorial Optimization Problems and their Approximability Properties","author":"G. Ausiello","year":"1999","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation. Combinatorial Optimization Problems and their Approximability Properties. Springer, Berlin (1999)"},{"key":"6_CR3","doi-asserted-by":"crossref","unstructured":"Baake, P., Wichmann, T.: On the economics of Internet peering. Netnomics\u00a01(1) (1999)","DOI":"10.1023\/A:1011449721395"},{"issue":"3","key":"6_CR4","doi-asserted-by":"publisher","first-page":"809","DOI":"10.1137\/S0097539798337716","volume":"30","author":"C.L. Barrett","year":"2000","unstructured":"Barrett, C.L., Jacob, R., Marathe, M.: Formal language constrained path problems. SIAM J. Comput.\u00a030(3), 809\u2013837 (2000)","journal-title":"SIAM J. Comput."},{"issue":"23","key":"6_CR5","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1137\/S0097539792225297","volume":"4","author":"E. Dahlhaus","year":"1994","unstructured":"Dahlhaus, E., Johnson, D., Papadimitriou, C., Seymour, P., Yannakakis, M.: The complexity of multiway cuts. SIAM J. Comput.\u00a04(23), 864\u2013894 (1994)","journal-title":"SIAM J. Comput."},{"key":"6_CR6","doi-asserted-by":"crossref","unstructured":"Di Battista, G., Patrignani, M., Pizzonia, M.: Computing the types of the relationships between autonomous systems. In: Proceedings of INFOCOM 2003 (2003)","DOI":"10.1109\/INFCOM.2003.1208668"},{"key":"6_CR7","unstructured":"Erlebach, T., Hall, A., Panconesi, A., Vukadinovi\u0107, D.: Cuts and disjoint paths in the valley-free path model. TIK-Report 180, Computer Engineering and Networks Laboratory (TIK), ETH Z\u00fcrich (2003), Available electronically at ftp:\/\/ftp.tik.ee.ethz.ch\/pub\/publications\/TIK-Report180.pdf"},{"key":"6_CR8","unstructured":"Erlebach, T., Hall, A., Schank, T.: Classifying customer-provider relationships in the Internet. In: Proceedings of the IASTED International Conference on Communications and Computer Networks, pp. 538\u2013545 (2002)"},{"issue":"2","key":"6_CR9","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","volume":"10","author":"S. Fortune","year":"1980","unstructured":"Fortune, S., Hopcroft, J., Willie, J.: The directed subgraph homeomorphism problem. Theoretical Computer Science\u00a010(2), 111\u2013121 (1980)","journal-title":"Theoretical Computer Science"},{"issue":"6","key":"6_CR10","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1109\/90.974527","volume":"9","author":"L. Gao","year":"2001","unstructured":"Gao, L.: On inferring Autonomous System relationships in the Internet. IEEE\/ACM Transactions on Networking\u00a09(6), 733\u2013745 (2001)","journal-title":"IEEE\/ACM Transactions on Networking"},{"key":"6_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1007\/3-540-58201-0_92","volume-title":"Automata, Languages, and Programming","author":"N. Garg","year":"1994","unstructured":"Garg, N., Vazirani, V., Yannakakis, M.: Multiway cuts in directed and node weighted graphs. In: Shamir, E., Abiteboul, S. (eds.) ICALP 1994. LNCS, vol.\u00a0820, pp. 487\u2013498. Springer, Heidelberg (1994)"},{"key":"6_CR12","unstructured":"Huston, G.: Interconnection, peering and settlements\u2014Part I. Internet Protocol Journal (March 1999)"},{"key":"6_CR13","unstructured":"Huston, G.: Interconnection, peering and settlements\u2014Part II. Internet Protocol Journal (June 1999)"},{"key":"6_CR14","doi-asserted-by":"crossref","unstructured":"Labovitz, C., Ahuja, A., Wattenhofer, R., Venkatachary, S.: The impact of Internet policy and topology on delayed routing convergence. In: Proceedings of INFOCOM 2001 (2001)","DOI":"10.1109\/INFCOM.2001.916775"},{"key":"6_CR15","unstructured":"Subramanian, L., Agarwal, S., Rexford, J., Katz, R.: Characterizing the Interenet hierarchy from multiple vantage points. In: Proceedings of INFOCOM 2002 (2002)"},{"key":"6_CR16","doi-asserted-by":"crossref","unstructured":"Tangmunarunkit, H., Govindan, R., Shenker, S.: Internet path inflation due to policy routing. In: Proceedings of SPIE ITCom 2001 (2001)","DOI":"10.1117\/12.434394"},{"key":"6_CR17","doi-asserted-by":"crossref","unstructured":"Tangmunarunkit, H., Govindan, R., Shenker, S., Estrin, D.: The impact of routing policy on Internet paths. In: Proceedings of INFOCOM 2001 (2001)","DOI":"10.1109\/INFCOM.2001.916262"},{"key":"6_CR18","unstructured":"Wanke, E.: The complexity of finding oriented paths in mixed graphs. Technical report, Institut f\u00fcr Informatik, Heinrich-Heine-Universit\u00e4t, D\u00fcsseldorf (2003)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial and Algorithmic Aspects of Networking"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11527954_6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:08:24Z","timestamp":1605643704000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11527954_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540278733","9783540318606"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/11527954_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}