{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T08:46:58Z","timestamp":1770972418587,"version":"3.50.1"},"publisher-location":"Boston, MA","reference-count":95,"publisher":"Springer US","isbn-type":[{"value":"9780387747583","type":"print"},{"value":"9780387747590","type":"electronic"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-0-387-74759-0_178","type":"book-chapter","created":{"date-parts":[[2008,8,25]],"date-time":"2008-08-25T11:03:26Z","timestamp":1219662206000},"page":"1005-1016","source":"Crossref","is-referenced-by-count":8,"title":["Feedback Set Problems"],"prefix":"10.1007","author":[{"given":"Paola","family":"Festa","sequence":"first","affiliation":[]},{"given":"Panos M.","family":"Pardalos","sequence":"additional","affiliation":[]},{"given":"Mauricio G.C.","family":"Resende","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"178_CR1_178","first-page":"142","volume-title":"ISAAC95, Algorithms and Computation. Lecture Notes Computedr Sci","author":"V Bafna","year":"1995","unstructured":"Bafna V, Berman P, Fujito T (1995) Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs. In:\n\tStaples J, Eades P, Katoh N, Moffat A (eds) ISAAC95, Algorithms and Computation. Lecture Notes Computedr Sci. Springer, Berlin, pp\n\t142\u2013151"},{"issue":"4","key":"178_CR2_178","doi-asserted-by":"publisher","first-page":"942","DOI":"10.1137\/S0097539796305109","volume":"27","author":"R. Bar-Yehuda","year":"1998","unstructured":"Bar-Yehuda R, Geiger D, Naor J, Roth RM (1998) Approximation algorithms for the vertex feedback set problem with applications to\n\tconstraint satisfaction and Bayesian inference. SIAM J Comput 27(4):942\u2013959","journal-title":"SIAM J. Comput."},{"key":"178_CR3_178","first-page":"60","volume-title":"Approximation algorithm for the loop cutset problem. 10th Conf. Uncertainty in Artificial Intelligence","author":"A Becker","year":"1994","unstructured":"Becker A, Geiger D (1994) Approximation\n      algorithm for the loop cutset problem. 10th Conf. Uncertainty in Artificial Intelligence. Morgan Kaufmann, San Mateo, pp 60\u201368"},{"key":"178_CR4_178","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/0004-3702(95)00004-6","volume":"83","author":"A. Becker","year":"1996","unstructured":"Becker A, Geiger D (1996) Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex\n\tfeedback set problem. Artif Intell 83:167\u2013188","journal-title":"Artif. Intell."},{"key":"178_CR5_178","doi-asserted-by":"crossref","first-page":"193","DOI":"10.4153\/CMB-1987-028-5","volume":"30","author":"J.A. Bondy","year":"1987","unstructured":"Bondy JA, Hopkins G, Staton W (1987) Lower bounds for induced forests in cubic graphs. Canad Math Bull\n\t30:193\u2013199","journal-title":"Canad. Math. Bull."},{"key":"178_CR6_178","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0020-0190(88)90168-8","volume":"28","author":"D.P. Bovet","year":"1988","unstructured":"Bovet DP, de Agostino S, Petreschi R (1988) Parallelism and the feedback vertex set problem. Inform Process Lett\n\t28:81\u201385","journal-title":"Inform. Process. Lett."},{"key":"178_CR7_178","first-page":"1","volume-title":"Lecture Notes Computer Sci","author":"A Brandst\u00e4dt","year":"1993","unstructured":"Brandst\u00e4dt A (1993) On improved time bounds for permutation graph problems. In: 18th Workshop on Graph-theoretic concepts in computer science, vol\u00a0657. In: Lecture Notes Computer Sci, vol\u00a0657. Wiesbaden-Naurod and Springer, Berlin, pp 1\u201310"},{"key":"178_CR8_178","first-page":"53","volume-title":"Fundamentals of Computing Theory. Lecture Notes Computer Sci","author":"A Brandst\u00e4dt","year":"1985","unstructured":"Brandst\u00e4dt A, Kratsch D (1985) On the restriction of some NP-complete graph problems to permutation graphs. In: Budach L (ed)\n\tFundamentals of Computing Theory. Lecture Notes Computer Sci. Springer, Berlin, pp 53\u201362"},{"key":"178_CR9_178","doi-asserted-by":"crossref","unstructured":"Breuer MA, Gupta R (1989) BALLAST: A\u00a0methodology for partial scan design. 19th Internat Symposium on Fault-Tolerant Computing, pp 118\u2013125","DOI":"10.1109\/FTCS.1989.105553"},{"key":"178_CR10_178","unstructured":"Cai M, Deng X, Zang W (1998)\n      A\u00a0TDI system and its application to approximation algorithm. 39th Annual Symposium on Foundations of Computer Sci"},{"key":"178_CR11_178","volume-title":"Lecture Notes Computer Sci","author":"M Cai","year":"1999","unstructured":"Cai M, Deng X, Zang W (1999) A\u00a0min-max\n      theorem on feedback vertex sets. Integer Programming and Combinatorial Optimization. Proc 7th Internat IPCO Conf. In: Lecture Notes Computer\n      Sci. Springer, Berlin"},{"key":"178_CR12_178","doi-asserted-by":"crossref","unstructured":"Chakradhar S, Balakrishnan A, Agrawal V (1994) An exact algorithm for selecting partial scan flip-flops. unpublished","DOI":"10.1145\/196244.196285"},{"key":"178_CR13_178","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/s002360050088","volume":"34","author":"M.S. Chang","year":"1997","unstructured":"Chang MS, Liang YD (1997) Minimum feedback vertex sets in cocomparability graphs and convex bipartite graphs. Acta Informatica\n\t34:337\u2013346","journal-title":"Acta Informatica"},{"key":"178_CR14_178","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/S0012-365X(96)00166-5","volume":"165\/166","author":"I. Charon","year":"1997","unstructured":"Charon I, Guenoche A, Hudry O, Wairgard F (1997) New results on the computation of median orders. Discret Math\n\t165\/166:139\u2013153","journal-title":"Discret Math."},{"key":"178_CR15_178","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1016\/0012-365X(88)90191-4","volume":"72","author":"R. Chen","year":"1988","unstructured":"Chen R, Guo X, Zhang F (1988) The z-transformation graphs of perfect matchings of hexagonal system. Discret Math\n\t72:405\u2013415","journal-title":"Discret Math."},{"issue":"4","key":"178_CR16_178","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1109\/12.54847","volume":"39","author":"K.T. Cheng","year":"1990","unstructured":"Cheng KT, Agrawal VD (1990) A\u00a0partial scan method for sequential circuits with feedback. IEEE Trans Comput 39(4):544\u2013548","journal-title":"IEEE Trans. Computers"},{"key":"178_CR17_178","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/S0167-6377(98)00021-2","volume":"22","author":"F.A. Chudak","year":"1998","unstructured":"Chudak FA, Goemans MX, Hochbaum D, Williamson DP (1998) A\u00a0primal-dual interpretation of two 2-approximation algorithms for the feedback\n\tvertex set problem in undirected graphs. Oper Res Lett 22:111\u2013118","journal-title":"Oper. Res. Lett."},{"key":"178_CR18_178","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V. Chv\u00e1tal","year":"1979","unstructured":"Chv\u00e1tal V (1979) A\u00a0greedy heuristic for the set covering problem. Math Oper Res 4:233\u2013235","journal-title":"Math. Oper. Res."},{"key":"178_CR19_178","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1002\/net.3230260205","volume":"26","author":"S.R. Coorg","year":"1995","unstructured":"Coorg SR, Rangan CP (1995) Feedback vertex set on cocomparability graphs. Networks 26:101\u2013111","journal-title":"Networks"},{"key":"178_CR20_178","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0166-218X(88)90086-8","volume":"22","author":"D.G. Corneil","year":"1988","unstructured":"Corneil DG, Fonlupt J (1988) The complexity of generalized clique covering. Discrete Appl Math 22:109\u2013118","journal-title":"Discrete Appl. Math."},{"key":"178_CR21_178","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/0004-3702(90)90046-3","volume":"41","author":"R. Dechter","year":"1990","unstructured":"Dechter R (1990) Enhancement schemes for constraint processing: Backjumping, learning, and cutset decomposition. Artif Intell\n\t41:273\u2013312","journal-title":"Artif. Intell."},{"key":"178_CR22_178","unstructured":"Dechter R, Pearl J (1987) The cycle cutset method for improving search performance in AI. In: 3rd IEEE on AI\n\tApplications"},{"key":"178_CR23_178","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1109\/TCS.1985.1085725","volume":"32","author":"J. Donald","year":"1995","unstructured":"Donald J, Elwin J, Hager R, Salamon P (1995) A\u00a0bad example for the minimum feedback vertex set problem. IEEE Trans Circuits and Systems\n\t32:491\u2013493","journal-title":"IEEE Trans. Circuits and Systems"},{"key":"178_CR24_178","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1137\/S0097539792228228","volume":"24","author":"R.G. Downey","year":"1995","unstructured":"Downey RG, Fellows MR (1995) Fixed-parameter tractability and completeness I: Basic results. SIAM J Comput\n\t24:873\u2013921","journal-title":"SIAM J. Comput."},{"key":"178_CR25_178","doi-asserted-by":"crossref","first-page":"3","DOI":"10.5486\/PMD.1962.9.1-2.02","volume":"9","author":"P. Erd\u00f6s","year":"1962","unstructured":"Erd\u00f6s P, Posa L (1962) On the maximal number of disjoint circiuts of a\u00a0graph. Publ Math Debrecen 9:3\u201312","journal-title":"Publ. Math. Debrecen"},{"key":"178_CR26_178","unstructured":"Even G, Naor JS, Zosin L. An 8-approximation algorithm for the subset feedback vertex problem proposed a\u00a08-approximation\n\talgorithm"},{"key":"178_CR27_178","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/PL00009191","volume":"20","author":"G. Even","year":"1998","unstructured":"Even G, Naor S, Schieber B, Sudan M (1998) Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica\n\t20:151\u2013174","journal-title":"Algorithmica"},{"key":"178_CR28_178","unstructured":"Even G, Naor S, Schieber B, Zosin L\n      (1996) Approximating minimum subset feedback sets in undirected graphs, with applications. 4th Israel Symposium on Theory of Computing and Systems, pp\n      78\u201388"},{"key":"178_CR29_178","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BF01096763","volume":"6","author":"T.A. Feo","year":"1995","unstructured":"Feo TA, Resende MG (1995) Greedy randomized adaptive search procedures. J\u00a0Global Optim 6:109\u2013133","journal-title":"J. Global Optim."},{"key":"178_CR30_178","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/978-1-4757-3023-4_4","volume":"4","author":"P. Festa","year":"1999","unstructured":"Festa P, Pardalos PM, Resende MGC (1999) Feedback set problems. In: Du D-Z, Pardalos PM (eds) Handbook Combinatorial Optim, vol\u00a04, pp\n\t209\u2013258","journal-title":"Handbook Combinatorial Optim."},{"key":"178_CR31_178","volume-title":"Fortran subroutines for approximate solution of feedback vertex set problems using GRASP","author":"P. Festa","year":"1999","unstructured":"Festa P, Pardalos PM, Resende MGC (1999) Fortran subroutines for approximate solution of feedback vertex set problems using\n\tGRASP. AT&T Lab Res, Florham Park"},{"key":"178_CR32_178","doi-asserted-by":"crossref","unstructured":"Funke M, Reinelt G (1996) A\u00a0polyhedral approach to the feedback vertex set problem. unpublished","DOI":"10.1007\/3-540-61310-2_33"},{"key":"178_CR33_178","volume-title":"Computers and intractability: A guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers\n      and intractability: A\u00a0guide to the theory of NP-completeness. Freeman, New York"},{"key":"178_CR34_178","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1016\/0020-0190(78)90015-7","volume":"7","author":"M.R. Garey","year":"1978","unstructured":"Garey MR, Tarjan RE (1978) A\u00a0linear-time algorithm for finding all feedback vertices. Inform Process Lett\n\t7:274\u2013276","journal-title":"Inform. Process. Lett."},{"issue":"2","key":"178_CR35_178","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1137\/S0097539793243016","volume":"25","author":"N. Garg","year":"1996","unstructured":"Garg N, Vazirani VV, Yannakakis M (1996) Approximate max-flow min-(multi) cut theorems and their applications. SIAM J Comput 25(2):235\u2013251","journal-title":"SIAM J. Comput."},{"key":"178_CR36_178","unstructured":"Gavril F (1977) Some NP-complete\n      problems on graphs. 11th Conf Inform Sci and Systems, Johns Hopkins Univ Press, Baltimore, pp 91\u201395"},{"key":"178_CR37_178","doi-asserted-by":"crossref","unstructured":"Goemans MX, Williamson DP (1996)\n      Primal-dual approximation algorithms for feedback problems in planar graphs. 5th MPS Conf Integer Programming and Combinatorial Optimization (IPCO), pp\n      147\u2013161","DOI":"10.1007\/3-540-61310-2_12"},{"key":"178_CR38_178","doi-asserted-by":"crossref","unstructured":"Gr\u00f6tschel M, Lov\u00e1sz L (1993)\n      Combinatorial optimization: A\u00a0survey. Techn Report, DIMACS Rutgers Univ 29","DOI":"10.1007\/978-3-642-78240-4_9"},{"key":"178_CR39_178","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric algorithms and combinatorial optimization","author":"M. Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel M, Lov\u00e1sz L, Schrijver A (1988) Geometric algorithms and combinatorial optimization. Springer, Berlin,\n\tpp 253\u2013254"},{"key":"178_CR40_178","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF01192587","volume":"6","author":"F. Harary","year":"1991","unstructured":"Harary F, Klein DJ, Zivkovic TP (1991) Graphical properties of polyhexes: Perfect matching vector and forcing. J\u00a0Math Chem\n\t6:295\u2013306","journal-title":"J. Math. Chem."},{"issue":"3","key":"178_CR41_178","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1137\/0211045","volume":"11","author":"D. Hochbaum","year":"1982","unstructured":"Hochbaum D (1982) Approximation algorithms for set covering and vertex cover problem. SIAM J Comput 11(3):555\u2013556","journal-title":"SIAM J. Comput."},{"key":"178_CR42_178","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1287\/opre.11.3.344","volume":"11","author":"T.C. Hu","year":"1963","unstructured":"Hu TC (1963) Multi-commodity network flows. Oper Res 11:344\u2013360","journal-title":"Oper. Res."},{"issue":"2","key":"178_CR43_178","first-page":"1","volume":"20","author":"G. Isaak","year":"1995","unstructured":"Isaak G (1995) Tournaments as feedback arc sets. Electronic J Combin 20(2):1\u201319","journal-title":"Electronic J. Combin."},{"key":"178_CR44_178","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D.S. Johnson","year":"1974","unstructured":"Johnson DS (1974) Approximation algorithms for combinatorial problems. J\u00a0Comput Syst Sci 9:256\u2013278","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"178_CR45_178","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1137\/0204007","volume":"4","author":"D.B. Johnson","year":"1975","unstructured":"Johnson DB (1975) Finding all the elementary circuits of a\u00a0directed graph. SIAM J Comput 4(1):77\u201384","journal-title":"SIAM J. Comput."},{"key":"178_CR46_178","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity Of Computer Computations","author":"R.M. Karp","year":"1972","unstructured":"Karp RM (1972) Reducibility among combinatorial problems. In: Miller RE, Thatcher JW (eds) Complexity Of Computer Computations. Plenum,\n\tNew York, pp 85\u2013103"},{"key":"178_CR47_178","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1109\/TCS.1980.1084814","volume":"27","author":"A.K. Kevorkian","year":"1980","unstructured":"Kevorkian AK (1980) General topological results on the construction of a\u00a0minimum essential set of a\u00a0directed graph. IEEE Trans Circuits\n\tand Systems 27:293\u2013304","journal-title":"IEEE Trans. Circuits and Systems"},{"key":"178_CR48_178","unstructured":"Kim H, Perl J. A\u00a0computational model for\n      combined causal and diagnostic reasoning in inference systems. 8th IJCAI, Morgan Kaufmann, San Mateo, pp 190\u2013193"},{"key":"178_CR49_178","doi-asserted-by":"publisher","first-page":"516","DOI":"10.1002\/jcc.540080432","volume":"8","author":"D.J. Klein","year":"1987","unstructured":"Klein DJ, Randi\u0107 M (1987) Innate degree of freedom of a\u00a0graph. J\u00a0Comput Chem 8:516\u2013521","journal-title":"J. Comput. Chem."},{"key":"178_CR50_178","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1103\/PhysRevB.43.723","volume":"43A","author":"D.J. Klein","year":"1991","unstructured":"Klein DJ, Zivkovi\u0107 TP, Valenti R (1991) Topological long-range order for resonating-valance-bond structures. Phys Rev B\n\t43A:723\u2013727","journal-title":"Phys. Rev. B"},{"key":"178_CR51_178","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/BF00137392","volume":"1","author":"A. Kunzmann","year":"1990","unstructured":"Kunzmann A, Wunderlich HJ (1990) An analytical approach to the partial scan problem. J\u00a0Electronic Testing: Th Appl\n\t1:163\u2013174","journal-title":"J. Electronic Testing: Th. Appl."},{"key":"178_CR52_178","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1111\/j.2517-6161.1988.tb01721.x","volume":"50","author":"S.L. Lauritzen","year":"1988","unstructured":"Lauritzen SL, Spiegelhalter DJ (1988) Local computations with probabilities on graphical structures and their application to expert\n\tsystems (with discussion). J\u00a0Royal Statist Soc B 50:157\u2013224","journal-title":"J. Royal Statist. Soc. B"},{"key":"178_CR53_178","doi-asserted-by":"crossref","unstructured":"Lee D, Reedy S (1990) On determining\n      scan flip-flops in partial scan designs. Internat Conf Computer Aided Design, pp 322\u2013325","DOI":"10.1109\/ICCAD.1990.129914"},{"key":"178_CR54_178","doi-asserted-by":"crossref","unstructured":"Leighton T, Rao S (1988) An approximate\n      max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. 29th Annual Symposium on Fundations of\n      Computer Sci, pp 422\u2013431","DOI":"10.1109\/SFCS.1988.21958"},{"key":"178_CR55_178","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1109\/TCT.1966.1082620","volume":"CT-13","author":"A. Lempel","year":"1966","unstructured":"Lempel A, Cederbaum I (1966) Minimum feedback arc and vertex sets of a\u00a0directed graph. IEEE Trans Circuit Theory\n\tCT-13:399\u2013403","journal-title":"IEEE Trans. Circuit Theory"},{"key":"178_CR56_178","doi-asserted-by":"publisher","first-page":"470","DOI":"10.1016\/0196-6774(88)90013-2","volume":"9","author":"H. Levy","year":"1988","unstructured":"Levy H, Lowe L (1988) A\u00a0contraction algorithm for finding small cycle cutsets. J\u00a0Algorithms 9:470\u2013493","journal-title":"J. Algorithms"},{"key":"178_CR57_178","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/0012-365X(93)E0184-6","volume":"140","author":"X. Li","year":"1995","unstructured":"Li X, Zhang F (1995) Hexagonal systems with forcing edges. Discret Math 140:253\u2013263","journal-title":"Discret Math."},{"key":"178_CR58_178","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/0020-0190(94)00133-2","volume":"52","author":"Y.D. Liang","year":"1994","unstructured":"Liang YD (1994) On the feedback vertex set problem in permutation graphs. Inform Process Lett 52:123\u2013129","journal-title":"Inform. Process. Lett."},{"key":"178_CR59_178","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0012-365X(94)00268-N","volume":"148","author":"J. Liu","year":"1996","unstructured":"Liu J, Zhao C (1996) A\u00a0new bound on the feedback vertex sets in cubic graphs. Discret Math 148:119\u2013131","journal-title":"Discret Math."},{"key":"178_CR60_178","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1016\/0022-0000(88)90009-8","volume":"37","author":"E.L. Lloyd","year":"1988","unstructured":"Lloyd EL, Soffa ML, Wang CC (1988) On locating minimum feedback vertex sets. J\u00a0Comput Syst Sci 37:292\u2013311","journal-title":"J. Comput. Syst. Sci."},{"key":"178_CR61_178","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/S0020-0190(96)00193-7","volume":"61","author":"ChinLung Lu","year":"1997","unstructured":"LuChin Lung, Tang Chuan Yi (1997) A\u00a0linear-time algorithm for the weighted feedback vertex problem on interval graphs. Inform Process\n\tLett 61:107\u2013111","journal-title":"Inform. Process. Lett."},{"key":"178_CR62_178","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1112\/jlms\/s2-17.3.369","volume":"17","author":"C.L. Lucchesi","year":"1978","unstructured":"Lucchesi CL, Younger DH (1978) A\u00a0minimax theorem for directed graphs. J\u00a0London Math Soc 17:369\u2013374","journal-title":"J. London Math. Soc."},{"key":"178_CR63_178","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/S0020-0190(98)00039-8","volume":"66","author":"F.L. Luccio","year":"1998","unstructured":"Luccio FL (1998) Almost exact minimum feedback vertex set in meshes and butterflies. Inform Process Lett\n\t66:59\u201364","journal-title":"Inform. Process. Lett."},{"key":"178_CR64_178","doi-asserted-by":"crossref","unstructured":"Lund C, Yannakakis M (1993) On the\n      hardness of approximating minimization problems. 25th ACM Symp on Theory Of Computing, pp 286\u2013293","DOI":"10.1145\/167088.167172"},{"key":"178_CR65_178","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0166-218X(92)90116-R","volume":"39","author":"M.V. Marathe","year":"1992","unstructured":"Marathe MV, Pandu Rangan C, Ravi R (1992) Efficient algorithms for generalized clique covering on interval graphs. Discrete Appl Math\n\t39:87\u201393","journal-title":"Discrete Appl. Math."},{"key":"178_CR66_178","unstructured":"Monien B, Schultz R (1981) Four\n      approximation algorithms for the feedback vertex set problems. 7th Conf Graph Theoretic Concepts of Computer Sci. Hauser, pp\n      315\u2013326"},{"key":"178_CR67_178","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/BF00993315","volume":"7","author":"T. Orenstein","year":"1995","unstructured":"Orenstein T, Kohavi Z, Pomeranz I (1995) An optimal algorithm for cycle breaking in directed graphs. J\u00a0Electronic Testing: Th Appl\n\t7:71\u201381","journal-title":"J. Electronic Testing: Th. Appl."},{"key":"178_CR68_178","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0012-365X(97)00266-5","volume":"190","author":"L. Pachter","year":"1998","unstructured":"Pachter L, Kim P (1998) Forcing matchings on square grids. Discret Math 190:287\u2013294","journal-title":"Discret Math."},{"key":"178_CR69_178","doi-asserted-by":"crossref","unstructured":"Papadimitriou C, Yannakakis M (1988)\n      Optimization, approximation and complexity classes. 20th Annual ACM Symp on Theory of Computing, pp 251\u2013277","DOI":"10.1145\/62212.62233"},{"key":"178_CR70_178","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1023\/A:1009736921890","volume":"2","author":"P.M. Pardalos","year":"1999","unstructured":"Pardalos PM, Qian T, Resende MGC (1999) A\u00a0greedy randomized adaptive search procedure for feedback vertex set. J\u00a0Combin Optim\n\t2:399\u2013412","journal-title":"J. Combin. Optim."},{"key":"178_CR71_178","unstructured":"Peleg D (1996) Local majority voting,\n      small coalitions, and controlling monopolies in graphs: A\u00a0review. 3rd Colloq Structural Information and Communication Complexity, pp\n      152\u2013169"},{"key":"178_CR72_178","unstructured":"Peleg D (1997) Size bounds for dynamic\n      monopolies. 4th Colloquium on Structural Information and Communication Complexity, Carleton Univ Press, Ottawa, pp\n      165\u2013175"},{"key":"178_CR73_178","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/0004-3702(86)90072-X","volume":"29","author":"J. Perl","year":"1986","unstructured":"Perl J (1986) Fusion, propagation and structuring in belief networks. Artif Intell 29:241\u2013288","journal-title":"Artif. Intell."},{"key":"178_CR74_178","unstructured":"Prais M, Ribeiro CC. Reactive GRASP: An application to a\u00a0matrix decomposition problem in TDMA traffic assignment"},{"key":"178_CR75_178","first-page":"341","volume-title":"Recent Advances in Global Optimization","author":"T Qian","year":"1995","unstructured":"Qian T, Ye Y, Pardalos PM (1995) A\u00a0pseudo-\u03f5 approximation algorithm for feedback vertex set. In: Floudas CA, Pardalos PM (eds) Recent\n\tAdvances in Global Optimization. Kluwer, Dordrecht, pp 341\u2013351"},{"key":"178_CR76_178","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/0196-6774(88)90022-3","volume":"9","author":"V. Ramachandran","year":"1988","unstructured":"Ramachandran V (1988) Finding a\u00a0minimum feedback arc set in reducible flow graphs. J\u00a0Algorithms 9:299\u2013313","journal-title":"J. Algorithms"},{"key":"178_CR77_178","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0196-6774(82)90020-7","volume":"3","author":"B. Rosen","year":"1982","unstructured":"Rosen B (1982) Robust linear algorithms for cutsets. J\u00a0Algorithms 3:205\u2013217","journal-title":"J. Algorithms"},{"key":"178_CR78_178","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/BF01200760","volume":"15","author":"P.D. Seymour","year":"1995","unstructured":"Seymour PD (1995) Packing directed circuits fractionally. Combinatorica 15:281\u2013288","journal-title":"Combinatorica"},{"issue":"4","key":"178_CR79_178","doi-asserted-by":"publisher","first-page":"645","DOI":"10.1137\/0208051","volume":"8","author":"A. Shamir","year":"1979","unstructured":"Shamir A (1979) A\u00a0linear time algorithm for finding minimum cutsets in reduced graphs. SIAM J Comput 8(4):645\u2013655","journal-title":"SIAM J. Comput."},{"key":"178_CR80_178","doi-asserted-by":"crossref","unstructured":"Shatcher RD, Andersen SK, Szolovits P\n      (1994) Global conditioning for probabilistic inference in belief networks. In: 10 Conf Uncertainty in AI, pp 514\u2013522","DOI":"10.1016\/B978-1-55860-332-5.50070-5"},{"key":"178_CR81_178","volume-title":"The logical design of operating systems","author":"A.C. Shaw","year":"1974","unstructured":"Shaw AC (1974) The logical design of operating systems. Prentice-Hall, Upper Saddle River"},{"key":"178_CR82_178","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1016\/0020-0190(79)90144-3","volume":"8","author":"D.A. Simovici","year":"1979","unstructured":"Simovici DA, Grigoras G (1979) Even initial feedback vertex set problem is NP-complete. Inform Process Lett\n\t8:64\u201366","journal-title":"Inform. Process. Lett."},{"issue":"1","key":"178_CR83_178","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1109\/TCS.1975.1083961","volume":"CAS-22","author":"G.W. Smith","year":"1975","unstructured":"Smith GW, Walford RB (1975) The identification of a\u00a0minimal feedback vertex set of a\u00a0directed graph. IEEE Trans Circuits and Systems\n\tCAS-22(1):9\u201314","journal-title":"IEEE Trans. Circuits and Systems"},{"key":"178_CR84_178","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1002\/jgt.3190120311","volume":"12","author":"E. Speckenmeyer","year":"1988","unstructured":"Speckenmeyer E (1988) On feedback vertex sets and nonseparating independent sets in cubic graphs. J\u00a0Graph Theory\n\t12:405\u2013412","journal-title":"J. Graph Theory"},{"key":"178_CR85_178","series-title":"Lecture Notes Computer Sci.","first-page":"218","volume-title":"On feedback problems in digraphs","author":"E. Speckenmeyer","year":"1989","unstructured":"Speckenmeyer E (1989) On feedback problems in digraphs. Lecture Notes Computer Sci, vol\u00a0411. Springer, Berlin, pp\n\t218\u2013231"},{"key":"178_CR86_178","doi-asserted-by":"crossref","unstructured":"Stamm H (1990) On feedback problems in a\u00a0planar digraph. In: M\u00f6hring R (ed) Graph-Theoretic Concepts in Computer Sci. Lecture\n\tNotes Computer Sci, vol\u00a0484. Springer, Berlin, pp 79\u201389","DOI":"10.1007\/3-540-53832-1_33"},{"key":"178_CR87_178","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R.E. Tarjan","year":"1972","unstructured":"Tarjan RE (1972) Depth first search and linear graph algorithms. SIAM J Comput 1:146\u2013160","journal-title":"SIAM J. Comput."},{"key":"178_CR88_178","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1016\/0012-365X(88)90226-9","volume":"72","author":"S. Ueno","year":"1988","unstructured":"Ueno S, Kajitani Y, Gotoh S (1988) On the nonseparating independent set problem and feedback set problem for graphs with no vertex\n\tdegree exceeding three. Discret Math 72:355\u2013360","journal-title":"Discret Math."},{"key":"178_CR89_178","unstructured":"Vazirani V. Approximation\n      algorithms. Manuscript College of Computing, Georgia Inst Techn"},{"issue":"2","key":"178_CR90_178","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1145\/3149.3159","volume":"32","author":"C. Wang","year":"1985","unstructured":"Wang C, Lloyd E, Soffa M (1985) Feedback vertex sets and cyclically reducible graphs. J\u00a0ACM 32(2):296\u2013313","journal-title":"J. ACM"},{"key":"178_CR91_178","doi-asserted-by":"crossref","unstructured":"Yannakakis M (1978) Node and\n      edge-deletion NP-complete problems. 10th Annual ACM Symp Theory of Computing, pp 253\u2013264","DOI":"10.1145\/800133.804355"},{"key":"178_CR92_178","doi-asserted-by":"crossref","unstructured":"Yannakakis M (Feb. 1994) Some open\n      problems in approximation. Second Italian Conf Algorithm and Complexity, CIAC'94, pp 33\u201339","DOI":"10.1007\/3-540-57811-0_4"},{"key":"178_CR93_178","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0020-0190(87)90107-4","volume":"24","author":"M. Yannakakis","year":"1987","unstructured":"Yannakakis M, Gavril F (1987) The maximum k-colorable subgraph problem for chordal graphs. Inform Process Lett\n\t24:133\u2013137","journal-title":"Inform. Process. Lett."},{"key":"178_CR94_178","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1109\/TCT.1963.1082116","volume":"CT-10","author":"D.H. Younger","year":"1963","unstructured":"Younger DH (1963) Minimum feedback arc set for a\u00a0directed graph. IEEE Trans Circuit Theory CT-10:238\u2013245","journal-title":"IEEE Trans. Circuit Theory"},{"key":"178_CR95_178","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/0012-365X(90)90165-E","volume":"85","author":"M. Zheng","year":"1990","unstructured":"Zheng M, Lu X (1990) On the maximum induced forests of a\u00a0connected cubic graph without triangles. Discret Math\n\t85:89\u201396","journal-title":"Discret Math."}],"container-title":["Encyclopedia of Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-74759-0_178","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,11]],"date-time":"2024-07-11T09:46:40Z","timestamp":1720691200000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-0-387-74759-0_178"}},"subtitle":["FSP"],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9780387747583","9780387747590"],"references-count":95,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-74759-0_178","relation":{},"subject":[],"published":{"date-parts":[[2008]]}}}