{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T01:36:28Z","timestamp":1787362588783,"version":"build-2736575974"},"reference-count":26,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>We consider the following network design problem that we call the Generalized Terminal Backup Problem: given a graph (or a hypergraph) $G_0=(V, {E}_0)$, a set of (at least 2) terminals $T\\subseteq V$, and a requirement $r(t)$ for every $t\\in T$, find a multigraph $G=(V,E)$ such that $\\lambda_{G_0+G}(t, T-t)\\ge r(t)$ for any $t\\in T$. In the minimum cost version the objective is to find $G$ minimizing the total cost $c(E)=\\sum_{uv\\in E}c(uv)$, given also costs $c(uv)\\ge 0$ for every pair $u,v\\in V$. In the degree-specified version the question is to decide whether such a $G$ exists, satisfying that the degree of $v \\in V$ is a prescribed value $m(v)$. The Terminal Backup Problem solved in [E. Anshelevich and A. Karagiozova, SIAM J. Comput., 40 (2011), pp. 678--708] is the special case where $G_0$ is the empty graph and $r(t)=1$ for every terminal $t\\in T$. We solve the Generalized Terminal Backup Problem in the following two cases. In the first case we solve the degree-specified version by a splitting-off theorem. This splitting-off theorem in turn provides the solution for the minimum cost version in the case when $c$ is node-induced, that is $c(uv)=w(u)+w(v)$ for some node weights $w:V\\to \\mathbb{R}_+$. In the second case we turn to the general minimum cost version, and we are able to solve it when $G_0$ is the empty graph. This includes the Terminal Backup Problem ($r\\equiv 1$) and the Maximum-Weight $b$-matching Problem ($T=V$). The solution depends on an interesting new variant of a theorem of Lov\u00e1sz and Cherkassky, and on the solution of the so-called Simplex Matching Problem. Our algorithms run in polynomial time for both problems.<\/jats:p>","DOI":"10.1137\/140972858","type":"journal-article","created":{"date-parts":[[2015,9,22]],"date-time":"2015-09-22T11:41:06Z","timestamp":1442922066000},"page":"1764-1782","source":"Crossref","is-referenced-by-count":5,"title":["The Generalized Terminal Backup Problem"],"prefix":"10.1137","volume":"29","author":[{"given":"Attila","family":"Bern\u00e1th","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yusuke","family":"Kobayashi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tatsuya","family":"Matsuoka","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,9,22]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1137\/090752699"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/S0036142993226983"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/s101070050033"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1007\/s101070050034"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-012-2548-8"},{"key":"atypb6","first-page":"1678","author":"Berna\u0301th A.","year":"2014","journal-title":"Philadelphia"},{"key":"atypb7","first-page":"143","volume":"13","author":"Cherkassky B. V.","year":"1977","journal-title":"Ekonom. Mat. Metody"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/0405003"},{"key":"atypb9","unstructured":"A. Frank,\n                      Connections in Combinatorial Optimization\n                      , Oxford University Press, Oxford, 2011."},{"key":"atypb10","first-page":"87","author":"Frank A.","year":"2009","journal-title":"Berlin"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2007.09.012"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2006.04.017"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170004"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2003.12.004"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2009.12.011"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/BF01902503"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/BF01226062"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.4064\/fm-10-1-96-115"},{"key":"atypb19","first-page":"224","volume":"47","author":"Miwa H.","year":"2004","journal-title":"J. Oper. Res. Soc. Japan"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1145\/1644015.1644020"},{"key":"atypb21","first-page":"139","author":"Pap G.","year":"2004","journal-title":"Berlin"},{"key":"atypb22","unstructured":"A. Schrijver,\n                      Combinatorial Optimization. Polyhedra and Efficiency\n                      , Algorithms Combin. 24, Springer-Verlag, Berlin, 2003."},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1007\/s101070050036"},{"key":"atypb24","first-page":"483","author":"Szigeti Z.","year":"2009","journal-title":"Berlin"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(87)90038-9"},{"key":"atypb26","first-page":"186","author":"Xu D.","year":"2008","journal-title":"NJ"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/140972858","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:18:17Z","timestamp":1787318297000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/140972858"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/140972858"],"URL":"https:\/\/doi.org\/10.1137\/140972858","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}