{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:16:39Z","timestamp":1761621399391},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2018,8,21]],"date-time":"2018-08-21T00:00:00Z","timestamp":1534809600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,4]]},"DOI":"10.1007\/s00453-018-0494-6","type":"journal-article","created":{"date-parts":[[2018,8,21]],"date-time":"2018-08-21T12:42:07Z","timestamp":1534855327000},"page":"1584-1614","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A Parameterized Algorithmics Framework for Degree Sequence Completion Problems in Directed Graphs"],"prefix":"10.1007","volume":"81","author":[{"given":"Robert","family":"Bredereck","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vincent","family":"Froese","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcel","family":"Koseler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcelo","family":"Garlet Millani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andr\u00e9","family":"Nichterlein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,8,21]]},"reference":[{"key":"494_CR1","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"RK Ahuja","year":"1993","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Upper Saddle River (1993)"},{"key":"494_CR2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090","volume-title":"Complexity Theory: A Modern Approach","author":"S Arora","year":"2009","unstructured":"Arora, S., Barak, B.: Complexity Theory: A Modern Approach. Cambridge University Press, Cambridge (2009)"},{"issue":"2","key":"494_CR3","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1137\/S0036142993226983","volume":"8","author":"J Bang-Jensen","year":"1995","unstructured":"Bang-Jensen, J., Frank, A., Jackson, B.: Preserving and increasing local edge-connectivity in mixed graphs. SIAM J. Discret. Math. 8(2), 155\u2013178 (1995)","journal-title":"SIAM J. Discret. Math."},{"issue":"3","key":"494_CR4","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1002\/jgt.22157","volume":"87","author":"J Bang-Jensen","year":"2018","unstructured":"Bang-Jensen, J., Huang, J., Zhu, X.: Completing orientations of partially oriented graphs. J. Graph Theory 87(3), 285\u2013304 (2018)","journal-title":"J. Graph Theory"},{"key":"494_CR5","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1016\/j.tcs.2016.02.004","volume":"622","author":"C Bazgan","year":"2016","unstructured":"Bazgan, C., Bredereck, R., Hartung, S., Nichterlein, A., Woeginger, G.J.: Finding large degree-anonymous subgraphs is hard. Theor. Comput. Sci. 622, 90\u2013110 (2016)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"494_CR6","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1007\/s10115-016-0947-7","volume":"50","author":"J Casas-Roma","year":"2017","unstructured":"Casas-Roma, J., Herrera-Joancomart\u00ed, J., Torra, V.: \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -degree anonymity and edge selection: improving data utility in large networks. Knowl. Inf. Syst. 50(2), 447\u2013474 (2017)","journal-title":"Knowl. Inf. Syst."},{"issue":"5","key":"494_CR7","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1016\/0016-0032(66)90301-2","volume":"281","author":"W-K Chen","year":"1966","unstructured":"Chen, W.-K.: On the realization of a \n                    \n                      \n                    \n                    $$(p, s)$$\n                    \n                      \n                        \n                          (\n                          p\n                          ,\n                          s\n                          )\n                        \n                      \n                    \n                  -digraph with prescribed degrees. J. Frankl. Inst. 281(5), 406\u2013422 (1966)","journal-title":"J. Frankl. Inst."},{"issue":"2","key":"494_CR8","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/s13278-012-0059-7","volume":"3","author":"S Chester","year":"2013","unstructured":"Chester, S., Kapron, B., Srivastava, G., Venkatesh, S.: Complexity of social network anonymization. Soc. Netw. Anal. Min. 3(2), 151\u2013166 (2013)","journal-title":"Soc. Netw. Anal. Min."},{"issue":"1","key":"494_CR9","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/s00453-012-9667-x","volume":"68","author":"M Cygan","year":"2014","unstructured":"Cygan, M., Marx, D., Pilipczuk, M., Pilipczuk, M., Schlotter, I.: Parameterized complexity of eulerian deletion problems. Algorithmica 68(1), 41\u201361 (2014)","journal-title":"Algorithmica"},{"key":"494_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, \u0141., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)"},{"issue":"1","key":"494_CR11","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1137\/110834810","volume":"27","author":"F Dorn","year":"2013","unstructured":"Dorn, F., Moser, H., Niedermeier, R., Weller, M.: Efficient algorithms for eulerian extension and rural postman. SIAM J. Discret. Math. 27(1), 75\u201394 (2013)","journal-title":"SIAM J. Discret. Math."},{"key":"494_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, Berlin (2013)"},{"key":"494_CR13","first-page":"264","volume":"11","author":"P Erd\u0151s","year":"1960","unstructured":"Erd\u0151s, P., Gallai, T.: Graphs with prescribed degrees of vertices (in Hungarian). Mat. Lapok 11, 264\u2013274 (1960)","journal-title":"Mat. Lapok"},{"key":"494_CR14","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"issue":"1","key":"494_CR15","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/BF02579200","volume":"7","author":"A Frank","year":"1987","unstructured":"Frank, A., Tardos, \u00c9.: An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica 7(1), 49\u201365 (1987)","journal-title":"Combinatorica"},{"issue":"6","key":"494_CR16","doi-asserted-by":"publisher","first-page":"1100","DOI":"10.1016\/j.jcss.2016.03.009","volume":"82","author":"V Froese","year":"2016","unstructured":"Froese, V., Nichterlein, A., Niedermeier, R.: Win-win kernelization for degree sequence completion problems. J. Comput. Syst. Sci. 82(6), 1100\u20131111 (2016)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"494_CR17","doi-asserted-by":"publisher","first-page":"831","DOI":"10.2140\/pjm.1960.10.831","volume":"10","author":"D Fulkerson","year":"1960","unstructured":"Fulkerson, D.: Zero-one matrices with zero trace. Pac. J. Math. 10(3), 831\u2013836 (1960)","journal-title":"Pac. J. Math."},{"key":"494_CR18","doi-asserted-by":"publisher","first-page":"1073","DOI":"10.2140\/pjm.1957.7.1073","volume":"7","author":"D Gale","year":"1957","unstructured":"Gale, D.: A theorem on flows in networks. Pac. J. Math. 7, 1073\u20131082 (1957)","journal-title":"Pac. J. Math."},{"key":"494_CR19","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 and Company, New York (1979)"},{"key":"494_CR20","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/j.tcs.2015.04.034","volume":"591","author":"PA Golovach","year":"2015","unstructured":"Golovach, P.A.: Editing to a graph of given degrees. Theor. Comput. Sci. 591, 72\u201384 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"494_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2016.12.007","volume":"665","author":"PA Golovach","year":"2017","unstructured":"Golovach, P.A., Mertzios, G.B.: Graph editing to a given degree sequence. Theor. Comput. Sci. 665, 1\u201312 (2017)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"494_CR22","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1093\/comjnl\/bxm039","volume":"51","author":"G Gutin","year":"2008","unstructured":"Gutin, G., Yeo, A.: Some parameterized problems on digraphs. Comput. J. 51(3), 363\u2013371 (2008)","journal-title":"Comput. J."},{"issue":"3","key":"494_CR23","first-page":"496","volume":"10","author":"S Hakimi","year":"1962","unstructured":"Hakimi, S.: On realizability of a set of integers as degrees of the vertices of a linear graph. I. J. SIAM 10(3), 496\u2013506 (1962)","journal-title":"J. SIAM"},{"issue":"4","key":"494_CR24","doi-asserted-by":"publisher","first-page":"1931","DOI":"10.1137\/130935756","volume":"29","author":"S Hartung","year":"2015","unstructured":"Hartung, S., Nichterlein, A.: NP-hardness and fixed-parameter tractability of realizing degree sequences with directed acyclic graphs. SIAM J. Discret. Math. 29(4), 1931\u20131960 (2015)","journal-title":"SIAM J. Discret. Math."},{"key":"494_CR25","doi-asserted-by":"crossref","unstructured":"Hartung, S., Hoffmann, C., Nichterlein, A.: Improved upper and lower bound heuristics for degree anonymization in social networks. In: Proceedings of the 13th international symposium on experimental algorithms (SEA\u00a0\u201914), vol. 8504 of LNCS, pp. 376\u2013387. Springer (2014)","DOI":"10.1007\/978-3-319-07959-2_32"},{"key":"494_CR26","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/j.ic.2014.12.017","volume":"243","author":"S Hartung","year":"2015","unstructured":"Hartung, S., Nichterlein, A., Niedermeier, R., Such\u00fd, O.: A refined complexity analysis of degree anonymization in graphs. Inf. Comput. 243, 249\u2013262 (2015)","journal-title":"Inf. Comput."},{"issue":"4","key":"494_CR27","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Karp, R.M.: An \n                    \n                      \n                    \n                    $$n^{5\/2}$$\n                    \n                      \n                        \n                          n\n                          \n                            5\n                            \/\n                            2\n                          \n                        \n                      \n                    \n                   algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2(4), 225\u2013231 (1973)","journal-title":"SIAM J. Comput."},{"key":"494_CR28","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1287\/moor.12.3.415","volume":"12","author":"R Kannan","year":"1987","unstructured":"Kannan, R.: Minkowski\u2019s convex body theorem and integer programming. Math. Oper. Res. 12, 415\u2013440 (1987)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"494_CR29","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0012-365X(73)90037-X","volume":"6","author":"D Kleitman","year":"1973","unstructured":"Kleitman, D., Wang, D.: Algorithms for constructing graphs and digraphs with given valences and factors. SIAM J. Discret. Math. 6(1), 79\u201388 (1973)","journal-title":"SIAM J. Discret. Math."},{"key":"494_CR30","unstructured":"Koseler, M.: Kernelization for degree-constraint editing on directed graphs. Bachelor thesis, TU Berlin (2015). URL \n                    http:\/\/fpt.akt.tu-berlin.de\/publications\/theses\/BA-marcel-koseler.pdf"},{"key":"494_CR31","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HW Lenstra","year":"1983","unstructured":"Lenstra, H.W.: Integer programming with a fixed number of variables. Math. Oper. Res. 8, 538\u2013548 (1983)","journal-title":"Math. Oper. Res."},{"key":"494_CR32","doi-asserted-by":"crossref","unstructured":"Leskovec, J., Horvitz, E.: Planetary-scale views on a large instant-messaging network. In: Proceedings of the 17th international conference on World Wide Web (WWW\u00a0\u201908), ACM, pp. 915\u2013924 (2008)","DOI":"10.1145\/1367497.1367620"},{"key":"494_CR33","doi-asserted-by":"crossref","unstructured":"Liu, K., Terzi, E.: Towards identity anonymization on graphs. In: Proceedings of the ACM SIGMOD international conference on management of data, SIGMOD \u201908, ACM, pp. 93\u2013106 (2008)","DOI":"10.1145\/1376616.1376629"},{"issue":"1","key":"494_CR34","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/j.jcss.2011.02.001","volume":"78","author":"L Mathieson","year":"2012","unstructured":"Mathieson, L., Szeider, S.: Editing graphs to satisfy degree constraints: a parameterized approach. J. Comput. Syst. Sci. 78(1), 179\u2013191 (2012)","journal-title":"J. Comput. Syst. Sci."},{"key":"494_CR35","unstructured":"Millani, M.G.: Algorithms and complexity for degree anonymization in directed graphs. Bachelor thesis, TU Berlin (2015). URL \n                    http:\/\/fpt.akt.tu-berlin.de\/publications\/theses\/BA-marcelo-millani.pdf"},{"issue":"2","key":"494_CR36","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/j.jda.2008.09.005","volume":"7","author":"H Moser","year":"2009","unstructured":"Moser, H., Thilikos, D.M.: Parameterized complexity of finding regular induced subgraphs. J. Discret. Algorithms 7(2), 181\u2013190 (2009)","journal-title":"J. Discret. Algorithms"},{"key":"494_CR37","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)"},{"key":"494_CR38","doi-asserted-by":"crossref","unstructured":"Orlin, J.B.: Max flows in O(nm) time, or better. In: Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC \u201913), ACM, pp. 765\u2013774 (2013)","DOI":"10.1145\/2488608.2488705"},{"issue":"2","key":"494_CR39","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1016\/j.jcss.2011.07.001","volume":"78","author":"M Weller","year":"2012","unstructured":"Weller, M., Komusiewicz, C., Niedermeier, R., Uhlmann, J.: On making directed graphs transitive. J. Comput. Syst. Sci. 78(2), 559\u2013574 (2012)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0494-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0494-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0494-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,20]],"date-time":"2019-08-20T23:22:45Z","timestamp":1566343365000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0494-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,21]]},"references-count":39,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,4]]}},"alternative-id":["494"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0494-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,8,21]]},"assertion":[{"value":"13 October 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 August 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 August 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}