{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,24]],"date-time":"2025-01-24T05:14:01Z","timestamp":1737695641932,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540748380"},{"type":"electronic","value":"9783540748397"}],"license":[{"start":{"date-parts":[[2007,1,1]],"date-time":"2007-01-01T00:00:00Z","timestamp":1167609600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-74839-7_31","type":"book-chapter","created":{"date-parts":[[2007,12,6]],"date-time":"2007-12-06T14:55:58Z","timestamp":1196952958000},"page":"328-340","source":"Crossref","is-referenced-by-count":5,"title":["The Complexity of Bottleneck Labeled Graph Problems"],"prefix":"10.1007","author":[{"given":"Refael","family":"Hassin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00e9r\u00f4me","family":"Monnot","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Danny","family":"Segev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"31_CR1","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1023\/B:JOCO.0000038913.96607.c2","volume":"8","author":"A.A. Ageev","year":"2004","unstructured":"Ageev, A.A., Sviridenko, M.: Pipage rounding: A new method of constructing algorithms with proven performance guarantee. Journal of Combinatorial Optimization\u00a08(3), 307\u2013328 (2004)","journal-title":"Journal of Combinatorial Optimization"},{"key":"31_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"862","DOI":"10.1007\/11561071_76","volume-title":"Algorithms \u2013 ESA 2005","author":"H. Aissi","year":"2005","unstructured":"Aissi, H., Bazgan, C., Vanderpooten, D.: Approximation complexity of min-max (regret) versions of shortest path, spanning tree, and knapsack. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 862\u2013873. Springer, Heidelberg (2005)"},{"key":"31_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1007\/11602613_79","volume-title":"Algorithms and Computation","author":"H. Aissi","year":"2005","unstructured":"Aissi, H., Bazgan, C., Vanderpooten, D.: Complexity of the min-max (regret) versions of cut problems. In: Deng, X., Du, D.-Z. (eds.) ISAAC 2005. LNCS, vol.\u00a03827, pp. 789\u2013798. Springer, Heidelberg (2005)"},{"key":"31_CR4","unstructured":"Aissi, H., Bazgan, C., Vanderpooten, D.: Pseudo-polynomial algorithms for min-max and min-max regret problems. In: 5th ISORA, pp. 171\u2013178 (2005)"},{"issue":"5","key":"31_CR5","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0167-6377(94)90043-4","volume":"16","author":"I. Averbakh","year":"1994","unstructured":"Averbakh, I., Berman, O.: Categorized bottleneck-minisum path problems on networks. Operations Research Letters\u00a016(5), 291\u2013297 (1994)","journal-title":"Operations Research Letters"},{"issue":"1","key":"31_CR6","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/s10107-003-0396-4","volume":"98","author":"D. Bertsimas","year":"2003","unstructured":"Bertsimas, D., Sim, M.: Robust discrete optimization and network flows. Mathematical Programming Series B\u00a098(1), 49\u201371 (2003)","journal-title":"Mathematical Programming Series B"},{"issue":"2","key":"31_CR7","doi-asserted-by":"crossref","first-page":"259","DOI":"10.7151\/dmgt.1053","volume":"17","author":"H. Broersma","year":"1997","unstructured":"Broersma, H., Li, X.: Spanning trees with many or few colors in edge-colored graphs. Discussiones Mathematicae Graph Theory\u00a017(2), 259\u2013269 (1997)","journal-title":"Discussiones Mathematicae Graph Theory"},{"key":"31_CR8","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. Australasian Journal on Combinatorics\u00a031, 299\u2013311 (2005)","journal-title":"Australasian Journal on Combinatorics"},{"issue":"3","key":"31_CR9","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/S0167-6377(02)00241-9","volume":"31","author":"T. Br\u00fcggemann","year":"2003","unstructured":"Br\u00fcggemann, T., Monnot, J., Woeginger, G.: Local search for the minimum label spanning tree problem with bounded color classes. Operations Research Letters\u00a031(3), 195\u2013201 (2003)","journal-title":"Operations Research Letters"},{"issue":"5","key":"31_CR10","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/S0020-0190(97)00127-0","volume":"63","author":"R.-S. Chang","year":"1997","unstructured":"Chang, R.-S., Leu, S.-J.: The minimum labeling spanning trees. Information Processing Letters\u00a063(5), 277\u2013282 (1997)","journal-title":"Information Processing Letters"},{"key":"31_CR11","series-title":"International Series in Operations Research and Management Science","volume-title":"Multiple Criteria Optimization: State of the Art Annotated Bibliographic Survey","year":"2002","unstructured":"Ehrgott, M., Gandibleux, X. (eds.): Multiple Criteria Optimization: State of the Art Annotated Bibliographic Survey. International Series in Operations Research and Management Science, vol.\u00a052. Kluwer Academic Publishers, Dordrecht (2002)"},{"key":"31_CR12","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979)"},{"key":"31_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"480","DOI":"10.1007\/11821069_42","volume-title":"Mathematical Foundations of Computer Science 2006","author":"R. Hassin","year":"2006","unstructured":"Hassin, R., Monnot, J., Segev, D.: Approximation algorithms and hardness results for labeled connectivity problems. In: Kr\u00e1lovi\u010d, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol.\u00a04162, pp. 480\u2013491. Springer, Heidelberg (2006)"},{"issue":"4","key":"31_CR14","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1145\/322092.322100","volume":"25","author":"A. Itai","year":"1978","unstructured":"Itai, A., Rodeh, M., Tanimoto, S.L.: Some matching problems for bipartite graphs. Journal of the ACM\u00a025(4), 517\u2013525 (1978)","journal-title":"Journal of the ACM"},{"issue":"1","key":"31_CR15","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1007\/BF02523689","volume":"18","author":"D.R. Karger","year":"1997","unstructured":"Karger, D.R., Motwani, R., Ramkumar, G.D.S.: On approximating the longest path in a graph. Algorithmica\u00a018(1), 82\u201398 (1997)","journal-title":"Algorithmica"},{"key":"31_CR16","doi-asserted-by":"crossref","unstructured":"Karzanov, A.V.: Maximum matchings of given weight in complete and complete bipartite graphs. Kibernetika\u00a01, 7\u201311 (1987), English translation in CYBNAW, 23, 8\u201313","DOI":"10.1007\/BF01068796"},{"key":"31_CR17","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2620-6","volume-title":"Robust Discrete Optimization and its Applications","author":"P. Kouvelis","year":"1997","unstructured":"Kouvelis, P., Yu, G.: Robust Discrete Optimization and its Applications. Kluwer Academic Publishers, Dordrecht (1997)"},{"key":"31_CR18","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"E.L. Lawler","year":"1976","unstructured":"Lawler, E.L.: Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York (1976)"},{"issue":"3","key":"31_CR19","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/j.ipl.2005.06.009","volume":"96","author":"J. Monnot","year":"2005","unstructured":"Monnot, J.: The labeled perfect matching in bipartite graphs. Information Processing Letters\u00a096(3), 81\u201388 (2005)","journal-title":"Information Processing Letters"},{"key":"31_CR20","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., Yannakakis, M.: On the approximability of trade-offs and optimal access of web sources. In: 41st FOCS, pp. 86\u201392 (2000)","DOI":"10.1109\/SFCS.2000.892068"},{"issue":"2","key":"31_CR21","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/0167-6377(92)90069-F","volume":"12","author":"A.P. Punnen","year":"1992","unstructured":"Punnen, A.P.: Traveling salesman problem under categorization. Operations Research Letters\u00a012(2), 89\u201395 (1992)","journal-title":"Operations Research Letters"},{"issue":"1","key":"31_CR22","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/S0305-0548(02)00181-8","volume":"31","author":"A.P. Punnen","year":"2004","unstructured":"Punnen, A.P.: On bottleneck assignment problems under categorization. Computers and Operations Research\u00a031(1), 151\u2013154 (2004)","journal-title":"Computers and Operations Research"},{"issue":"2","key":"31_CR23","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/0166-218X(92)90165-7","volume":"39","author":"M.B. Richey","year":"1992","unstructured":"Richey, M.B., Punnen, A.P.: Minimum perfect bipartite matchings and spanning trees under categorization. Discrete Applied Mathematics\u00a039(2), 147\u2013153 (1992)","journal-title":"Discrete Applied Mathematics"},{"key":"31_CR24","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1002\/mcda.4020030204","volume":"3","author":"E.L. Ulungu","year":"1994","unstructured":"Ulungu, E.L., Teghem, J.: Multi-objective combinatorial optimization problems: A survey. Journal of Multi-Criteria Decision Analysis\u00a03, 83\u2013104 (1994)","journal-title":"Journal of Multi-Criteria Decision Analysis"},{"issue":"8","key":"31_CR25","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1038\/sj\/jors\/0410802","volume":"41","author":"D.J. White","year":"1990","unstructured":"White, D.J.: A bibliography on the applications of mathematical programming multiple-objective methods. Journal of the Operational Research Society\u00a041(8), 669\u2013691 (1990)","journal-title":"Journal of the Operational Research Society"},{"issue":"1-3","key":"31_CR26","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/S0166-218X(01)00300-6","volume":"121","author":"T. Yi","year":"2002","unstructured":"Yi, T., Murty, K.G., Spera, C.: Matchings in colored bipartite networks. Discrete Applied Mathematics\u00a0121(1-3), 261\u2013277 (2002)","journal-title":"Discrete Applied Mathematics"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74839-7_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,23]],"date-time":"2025-01-23T08:16:39Z","timestamp":1737620199000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74839-7_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540748380","9783540748397"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74839-7_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}