{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,6]],"date-time":"2025-07-06T08:10:09Z","timestamp":1751789409801,"version":"3.41.0"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319983547"},{"type":"electronic","value":"9783319983554"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-98355-4_12","type":"book-chapter","created":{"date-parts":[[2018,8,8]],"date-time":"2018-08-08T10:34:57Z","timestamp":1533724497000},"page":"191-215","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Sequence Hypergraphs: Paths, Flows, and Cuts"],"prefix":"10.1007","author":[{"given":"Kate\u0159ina","family":"B\u00f6hmov\u00e1","sequence":"first","affiliation":[]},{"given":"J\u00e9r\u00e9mie","family":"Chalopin","sequence":"additional","affiliation":[]},{"given":"Mat\u00fa\u0161","family":"Mihal\u00e1k","sequence":"additional","affiliation":[]},{"given":"Guido","family":"Proietti","sequence":"additional","affiliation":[]},{"given":"Peter","family":"Widmayer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,8,9]]},"reference":[{"key":"12_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1007\/3-540-45446-2_20","volume-title":"Theoretical Computer Science","author":"G Ausiello","year":"2001","unstructured":"Ausiello, G., Franciosa, P.G., Frigioni, D.: Directed hypergraphs: problems, algorithmic results, and a novel decremental approach. ICTCS 2001. LNCS, vol. 2202, pp. 312\u2013328. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-45446-2_20"},{"unstructured":"Ausiello, G., Giaccio, R., Italiano, G.F., Nanni, U.: Optimal traversal of directed hypergraphs. Technical report (1992)","key":"12_CR2"},{"key":"12_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1007\/3-540-63938-1_87","volume-title":"Graph Drawing","author":"J Berry","year":"1997","unstructured":"Berry, J., Dean, N., Goldberg, M., Shannon, G., Skiena, S.: Graph drawing and manipulation with LINK. In: DiBattista, G. (ed.) GD 1997. LNCS, vol. 1353, pp. 425\u2013437. Springer, Heidelberg (1997). https:\/\/doi.org\/10.1007\/3-540-63938-1_87"},{"key":"12_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1007\/978-3-319-34171-2_8","volume-title":"Computer Science \u2013 Theory and Applications","author":"K B\u00f6hmov\u00e1","year":"2016","unstructured":"B\u00f6hmov\u00e1, K., Mihal\u00e1k, M., Pr\u00f6ger, T., Sacomoto, G., Sagot, M.-F.: Computing and listing st-paths in public transportation networks. In: Kulikov, A.S., Woeginger, G.J. (eds.) CSR 2016. LNCS, vol. 9691, pp. 102\u2013116. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-34171-2_8"},{"key":"12_CR5","first-page":"299","volume":"31","author":"H Broersma","year":"2005","unstructured":"Broersma, H., Li, X., Woeginger, G., Zhang, S.: Paths and cycles in colored graphs. Australas. J. Comb. 31, 299\u2013311 (2005)","journal-title":"Australas. J. Comb."},{"unstructured":"Carr, R.D., Doddi, S., Konjevod, G., Marathe, M.V.: On the red-blue set cover problem. In: SODA 2000, vol. 9, pp. 345\u2013353. Citeseer (2000)","key":"12_CR6"},{"issue":"02","key":"12_CR7","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1142\/S0129626407002958","volume":"17","author":"D Coudert","year":"2007","unstructured":"Coudert, D., Datta, P., P\u00e9rennes, S., Rivano, H., Voge, M.E.: Shared risk resource group complexity and approximability issues. Parallel Process. Lett. 17(02), 169\u2013184 (2007)","journal-title":"Parallel Process. Lett."},{"doi-asserted-by":"crossref","unstructured":"Coudert, D., P\u00e9rennes, S., Rivano, H., Voge, M.E.: Combinatorial optimization in networks with shared risk link groups. Research report, INRIA, October 2015","key":"12_CR8","DOI":"10.46298\/dmtcs.1297"},{"doi-asserted-by":"crossref","unstructured":"Crescenzi, P., Kann, V., Halld\u00f3rsson, M., Karpinski, M., Woeginger, G.: A compendium of NP optimization problems (1997). http:\/\/www.nada.kth.se\/~viggo\/problemlist\/compendium.html","key":"12_CR9","DOI":"10.1007\/3-540-63248-4_10"},{"doi-asserted-by":"crossref","unstructured":"Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: STOC 2014, pp. 624\u2013633. ACM, New York (2014)","key":"12_CR10","DOI":"10.1145\/2591796.2591884"},{"issue":"4","key":"12_CR11","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1109\/TIT.1956.1056816","volume":"2","author":"P Elias","year":"1956","unstructured":"Elias, P., Feinstein, A., Shannon, C.E.: A note on the maximum flow through a network. IRE Trans. Inf. Theory 2(4), 117\u2013119 (1956)","journal-title":"IRE Trans. Inf. Theory"},{"issue":"1","key":"12_CR12","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/BF02579153","volume":"4","author":"PL Erd\u0151s","year":"1984","unstructured":"Erd\u0151s, P.L., Frankl, P., Katona, G.O.: Intersecting sperner families and their convex hulls. Combinatorica 4(1), 21\u201334 (1984)","journal-title":"Combinatorica"},{"key":"12_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/978-3-642-11409-0_8","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"MR Fellows","year":"2010","unstructured":"Fellows, M.R., Guo, J., Kanj, I.A.: The parameterized complexity of some minimum label problems. In: Paul, C., Habib, M. (eds.) WG 2009. LNCS, vol. 5911, pp. 88\u201399. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-11409-0_8"},{"issue":"2","key":"12_CR14","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/0166-218X(93)90045-P","volume":"42","author":"G Gallo","year":"1993","unstructured":"Gallo, G., Longo, G., Pallottino, S., Nguyen, S.: Directed hypergraphs and applications. Discrete Appl. Math. 42(2), 177\u2013201 (1993)","journal-title":"Discrete Appl. Math."},{"key":"12_CR15","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)"},{"key":"12_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1007\/978-3-642-38233-8_22","volume-title":"Algorithms and Complexity","author":"PW Goldberg","year":"2013","unstructured":"Goldberg, P.W., McCabe, A.: Shortest paths with bundles and non-additive weights is hard. In: Spirakis, P.G., Serna, M. (eds.) CIAC 2013. LNCS, vol. 7878, pp. 264\u2013275. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-38233-8_22"},{"issue":"4","key":"12_CR17","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/s10878-007-9044-x","volume":"14","author":"R Hassin","year":"2007","unstructured":"Hassin, R., Monnot, J., Segev, D.: Approximation algorithms and hardness results for labeled connectivity problems. J. Comb. Optim. 14(4), 437\u2013453 (2007)","journal-title":"J. Comb. Optim."},{"issue":"3","key":"12_CR18","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1109\/TCOMM.2003.809779","volume":"51","author":"JQ Hu","year":"2003","unstructured":"Hu, J.Q.: Diverse routing in optical mesh networks. IEEE Trans. Commun. 51(3), 489\u2013494 (2003)","journal-title":"IEEE Trans. Commun."},{"issue":"3","key":"12_CR19","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci. 74(3), 335\u2013349 (2008)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"12_CR20","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/S0020-0190(98)00034-9","volume":"66","author":"SO Krumke","year":"1998","unstructured":"Krumke, S.O., Wirth, H.C.: On the minimum label spanning tree problem. Inf. Process. Lett. 66(2), 81\u201385 (1998)","journal-title":"Inf. Process. Lett."},{"doi-asserted-by":"crossref","unstructured":"Wachman, G., Khardon, R.: Learning from interpretations: a rooted kernel for ordered hypergraphs. In: Proceedings of the 24th International Conference on Machine Learning, pp. 943\u2013950. ACM (2007)","key":"12_CR21","DOI":"10.1145\/1273496.1273615"},{"doi-asserted-by":"crossref","unstructured":"Yuan, S., Varma, S., Jue, J.P.: Minimum-color path problems for reliability in mesh networks. In: INFOCOM 2005, vol. 4, pp. 2658\u20132669. IEEE (2005)","key":"12_CR22","DOI":"10.1109\/INFCOM.2005.1498549"},{"issue":"2","key":"12_CR23","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1007\/s10878-009-9222-0","volume":"21","author":"P Zhang","year":"2011","unstructured":"Zhang, P., Cai, J.Y., Tang, L.Q., Zhao, W.B.: Approximation and hardness results for label cut and related problems. J. Comb. Optim. 21(2), 192\u2013208 (2011)","journal-title":"J. Comb. Optim."}],"container-title":["Lecture Notes in Computer Science","Adventures Between Lower Bounds and Higher Altitudes"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-98355-4_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,6]],"date-time":"2025-07-06T07:38:15Z","timestamp":1751787495000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-98355-4_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319983547","9783319983554"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-98355-4_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"9 August 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}