{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T09:46:00Z","timestamp":1743068760034,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642112683"},{"type":"electronic","value":"9783642112690"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-11269-0_18","type":"book-chapter","created":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T08:36:15Z","timestamp":1259656575000},"page":"222-233","source":"Crossref","is-referenced-by-count":5,"title":["Fixed-Parameter Algorithms in Analysis of Heuristics for Extracting Networks in Linear Programs"],"prefix":"10.1007","author":[{"given":"Gregory","family":"Gutin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Karapetyan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Igor","family":"Razgon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"18_CR1","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/s00224-007-1328-0","volume":"41","author":"F.N. Abu-Khzam","year":"2007","unstructured":"Abu-Khzam, F.N., Fellows, M.R., Langston, M., Suters, W.H.: Crown Structures for Vertex Cover Kernelization. Theory of Computing Systems\u00a041, 411\u2013430 (2007)","journal-title":"Theory of Computing Systems"},{"key":"18_CR2","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/s00453-006-1214-1","volume":"45","author":"F.N. Abu-Khzam","year":"2006","unstructured":"Abu-Khzam, F.N., Langston, M., Shanbhag, P., Symons, C.T.: Scalable Parallel Algorithms for FPT Problems. Algorithmica\u00a045, 269\u2013284 (2006)","journal-title":"Algorithmica"},{"key":"18_CR3","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1016\/0377-2217(93)90321-D","volume":"67","author":"B.M. Baker","year":"1993","unstructured":"Baker, B.M., Maye, P.J.: A Heuristic for Finding Embedded Network Structure in Mathematical Programmes. Europ. Jour. Oper. Res.\u00a067, 52\u201363 (1993)","journal-title":"Europ. Jour. Oper. Res."},{"key":"18_CR4","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1016\/0167-6377(82)90038-4","volume":"1","author":"J.J. Bartholdi","year":"1982","unstructured":"Bartholdi, J.J.: A Good Submatrix is Hard to Find. Oper. Res. Letters\u00a01, 190\u2013193 (1982)","journal-title":"Oper. Res. Letters"},{"key":"18_CR5","series-title":"Lecture Notes in Computer Science","first-page":"297","volume-title":"Experimental Algorithms","author":"N. Betzler","year":"2007","unstructured":"Betzler, N., H\u00fcffner, F., Niedermeier, R.: Optimal edge deletions for signed graph balancing. In: Demetrescu, C. (ed.) WEA 2007. LNCS, vol.\u00a04525, pp. 297\u2013310. Springer, Heidelberg (2007)"},{"key":"18_CR6","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1287\/mnsc.34.3.342","volume":"34","author":"R.E. Bixby","year":"1988","unstructured":"Bixby, R.E., Fourer, R.: Finding Embedded Network Rows in Linear Programs I. Extraction Heuristics. Manag. Science\u00a034, 342\u2013376 (1988)","journal-title":"Manag. Science"},{"key":"18_CR7","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1287\/moor.5.3.321","volume":"5","author":"R.E. Bixby","year":"1980","unstructured":"Bixby, R.E., Cunningham, W.H.: Converting Linear Programs to Network Problems. Math. Oper. Res.\u00a05, 321\u2013356 (1980)","journal-title":"Math. Oper. Res."},{"key":"18_CR8","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/BF02591728","volume":"29","author":"G.G. Brown","year":"1984","unstructured":"Brown, G.G., Wright, W.G.: Automatic Identification of Embedded Network Rows in Large-Scale Optimization Models. Math. Prog.\u00a029, 41\u201356 (1984)","journal-title":"Math. Prog."},{"key":"18_CR9","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Simplicity is beauty: Improved upper bounds for vertex cover. Tech. Report TR05-008, DePaul University, Chicago IL (2005)"},{"key":"18_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/11764298_23","volume-title":"Experimental Algorithms","author":"B. DasGupta","year":"2006","unstructured":"DasGupta, B., Enciso, G.A., Sontag, E.D., Zhang, Y.: Algorithmic and complexity results for decompositions of biological networks into monotone subsystems. In: \u00c0lvarez, C., Serna, M. (eds.) WEA 2006. LNCS, vol.\u00a04007, pp. 253\u2013264. Springer, Heidelberg (2006)"},{"key":"18_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"key":"18_CR12","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"key":"18_CR13","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1023\/A:1008791601215","volume":"15","author":"N. G\u00fclp\u0131nar","year":"2000","unstructured":"G\u00fclp\u0131nar, N., Gutin, G., Mitra, G., Maros, I.: Detecting Embedded Pure Network Structures by Using GUB and Independent Set Algorithms. Comput. Optim. Applic.\u00a015, 235\u2013247 (2000)","journal-title":"Comput. Optim. Applic."},{"key":"18_CR14","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1016\/S0166-218X(03)00361-5","volume":"137","author":"N. G\u00fclp\u0131nar","year":"2004","unstructured":"G\u00fclp\u0131nar, N., Gutin, G., Mitra, G., Zverovitch, A.: Extracting Pure Network Submatrices in Linear Programs Using Signed Graphs. Discrete Applied Mathematics\u00a0137, 359\u2013372 (2004)","journal-title":"Discrete Applied Mathematics"},{"key":"18_CR15","first-page":"58","volume":"6","author":"G. Gutin","year":"2003","unstructured":"Gutin, G., Zverovitch, A.: Extracting pure network submatrices in linear programs using signed graphs, Part 2. Communications of DQM\u00a06, 58\u201365 (2003)","journal-title":"Communications of DQM"},{"key":"#cr-split#-18_CR16.1","unstructured":"Hansen, P.: Labelling Algorithms for Balance in Signed Graphs. In: Probl\u00e9mes Combinatoires et Theorie des Graphes, Colloq. Internat., Orsay, pp. 215-217 (1976)"},{"key":"#cr-split#-18_CR16.2","unstructured":"Colloques Internat. du CNRS 260 Paris (1978)"},{"key":"18_CR17","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0165-4896(80)90010-4","volume":"1","author":"F. Harary","year":"1980","unstructured":"Harary, F., Kabell, J.A.: A Simple Algorithm to Detect Balance in Signed Graphs. Math. Social Science\u00a01, 131\u2013136 (1980-1981)","journal-title":"Math. Social Science"},{"key":"18_CR18","series-title":"Annals Math. Studies","first-page":"247","volume-title":"Linear Inequalities and Related Systems","author":"I. Heller","year":"1956","unstructured":"Heller, I., Tompkins, C.B.: An Extension of a Theorem of Dantzig\u2019s. In: Kuhn, H.W., Tucker, A.W. (eds.) Linear Inequalities and Related Systems. Annals Math. Studies, vol.\u00a038, pp. 247\u2013252. Princeton Univ. Press, Princeton (1956)"},{"key":"18_CR19","unstructured":"Hsu, A.C., Fourer, R.: Identification of Embedded Network Structure in Linear Programming Models. GSIA Working Paper, 1997-58"},{"key":"18_CR20","doi-asserted-by":"crossref","first-page":"77","DOI":"10.7155\/jgaa.00177","volume":"13","author":"F. H\u00fcffner","year":"2009","unstructured":"H\u00fcffner, F.: Algorithm Engineering for Optimal Graph Bipartization. Journal of Graph Algorithms and Applications\u00a013, 77\u201398 (2009)","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"18_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/978-3-540-79719-7_15","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2008","author":"S. Kottler","year":"2008","unstructured":"Kottler, S., Kaufmann, M., Sinz, C.: Computation of Renameable Horn Backdoors. In: Kleine B\u00fcning, H., Zhao, X. (eds.) SAT 2008. LNCS, vol.\u00a04996, pp. 154\u2013160. Springer, Heidelberg (2008)"},{"key":"18_CR22","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":"18_CR23","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0020-0190(92)90248-T","volume":"44","author":"V.T.. Paschos","year":"1992","unstructured":"Paschos, V.T.: A \u0394\/2-Approximation for the Maximum Independent Set Problem. Inform. Proc. Let.\u00a044, 11\u201313 (1992)","journal-title":"Inform. Proc. Let."},{"key":"18_CR24","unstructured":"Razgon, I., O\u2019Sullivan, B.: Almost 2-SAT is fixed-parameter tractable. Journal of Computer and System Sciences (in press)"},{"key":"18_CR25","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/j.orl.2003.10.009","volume":"32","author":"B. Reed","year":"2004","unstructured":"Reed, B., Smith, K., Vetta, A.: Finding odd cycle transversals. Operations Research Letters\u00a032, 299\u2013301 (2004)","journal-title":"Operations Research Letters"},{"key":"18_CR26","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0166-218X(82)90033-6","volume":"4","author":"T. Zaslavsky","year":"1982","unstructured":"Zaslavsky, T.: Signed Graphs. Discete Applied Math.\u00a04, 47\u201374 (1982)","journal-title":"Discete Applied Math."}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-11269-0_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,8]],"date-time":"2023-02-08T22:11:24Z","timestamp":1675894284000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-11269-0_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642112683","9783642112690"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-11269-0_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}