{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,26]],"date-time":"2026-07-26T01:41:36Z","timestamp":1785030096594,"version":"3.55.0"},"publisher-location":"Boston, MA","reference-count":92,"publisher":"Springer US","isbn-type":[{"value":"9781441948137","type":"print"},{"value":"9781475730234","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/978-1-4757-3023-4_4","type":"book-chapter","created":{"date-parts":[[2013,2,21]],"date-time":"2013-02-21T08:28:50Z","timestamp":1361435330000},"page":"209-258","source":"Crossref","is-referenced-by-count":90,"title":["Feedback Set Problems"],"prefix":"10.1007","author":[{"given":"Paola","family":"Festa","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Panos M.","family":"Pardalos","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mauricio G. C.","family":"Resende","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"4_CR1","unstructured":"V. Bafna, P. Berman, and T. lijito, Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs, in ISAAC95, Algorithms and Computation,J. Staples, P. Eades, N. Katoh and A. Moffat Eds., Lecture Notes in Computer Science Vol.1004, Springer-Verlag (1995) pp. 142\u2013151."},{"key":"4_CR2","unstructured":"R. Bar-Yehuda, D. Geiger, J. Naor, and R.M. Roth, Approximation algorithms for the vertex feedback set problem with applications to constraint satisfaction and Bayesian inference, A preliminary version of this paper appeared in the Proc. of the 5t h Annual ACM-SIAM Symp. on Discrete Algorithms, pp. 344\u2013354, (1994) and subsequently published in SIAM J. Comput. Vol. 27 No. 4 (1998) pp. 942\u2013959."},{"key":"4_CR3","unstructured":"A. Becker, and D. Geiger, Approximation algorithm for the loop cut-set problem, in Proceedings of the 10th Conference on Uncertainty in Artificial Intelligence Morgan Kaufman (1994) pp. 60\u201368."},{"key":"4_CR4","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/0004-3702(95)00004-6","volume":"83","author":"A Becker","year":"1996","unstructured":"A. Becker, and D. Geiger, Optimization of Pearl\u2019s method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem, Artificial Intelligence Vol. 83 (1996) pp. 167\u2013188.","journal-title":"Artificial Intelligence"},{"key":"4_CR5","doi-asserted-by":"publisher","first-page":"193","DOI":"10.4153\/CMB-1987-028-5","volume":"30","author":"JA Bondy","year":"1987","unstructured":"J. A. Bondy, G. Hopkins, and W. Staton, Lower bounds for induced forests in cubic graphs, Gonad. Math. Bull. Vol. 30 (1987) pp. 193\u2013199.","journal-title":"Gonad. Math. Bull"},{"key":"4_CR6","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0020-0190(88)90168-8","volume":"28","author":"DP Bovet","year":"1988","unstructured":"D.P. Bovet, S. de Agostino, and R. Petreschi, Parallelism and the feedback vertex set problem, Information Processing Letters Vol. 28 (1988) pp. 81\u201385.","journal-title":"Information Processing Letters"},{"key":"4_CR7","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/BFb0028791","volume-title":"Proc. of Fundamentals of Computing Theory, Lecture Notes in Comp. Sci. Vol.199","author":"A Brandst\u00e4dt","year":"1985","unstructured":"A. Brandst\u00e4dt, and D. Kratsch, On the restriction of some NP-complete graph problems to permutation graphs, in Proc. of Fundamentals of Computing Theory, Lecture Notes in Comp. Sci. Vol.199 ( L. Budach, Ed. Springer-Verlag, Berlin, 1985 ) pp. 53\u201362."},{"key":"4_CR8","unstructured":"A. Brandst\u00e4dt, On improved time bounds for permutation graph problems, in Proc. of the 18 th Workshop on Graph-theoretic concepts in computer science, (Wiesbaden-Naurod, 1992) Springer-Verlag LNCS 657 (1993) pp. 1\u201310."},{"key":"4_CR9","unstructured":"M.A. Breuer, and R. Gupta, BALLAST: A methodology for partial scan design, in Proc. of the 19 th Int. Symposium on Fault-Tolerant Computing (1989) pp. 118\u2013125"},{"key":"4_CR10","unstructured":"M. Cai, X. Deng, and W. Zang, A TDI system and its application to approximation algorithm, in Proc. of the 39th Annual Symposium on Foundations of Computer Science, Palo Alto, California, November 8\u201311, (1998)."},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"M. Cai, X. Deng, and W. Zang, A min-max theorem on feedback vertex sets, to appear in Integer Programming and Combinatorial Optimization: Proceedings 7th International IPCO Conference, Lecture Notes in Computer Science Springer-Verlag (1999)","DOI":"10.1007\/3-540-48777-8_6"},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"S Chakradhar, A. Balakrishnan, and V. Agrawal, An exact algorithm for selecting partial scan flip-flops, Manuscript (1994).","DOI":"10.1145\/196244.196285"},{"key":"4_CR13","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/s002360050088","volume":"34","author":"MS Chang","year":"1997","unstructured":"M.S. Chang, Y.D. Liang, Minimum feedback vertex sets in cocomparability graphs and convex bipartite graphs, Acta Informatica Vol. 34 (1997) pp. 337\u2013346.","journal-title":"Acta Informatica"},{"issue":"166","key":"4_CR14","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/S0012-365X(96)00166-5","volume":"165","author":"I Charon","year":"1997","unstructured":"I. Charon, A. Guenoche, O. Hudry, and F. Wairgard, New results on the computation of median orders, Discr. Math. Vol. 165 \/166 (1997) pp. 139\u2013153.","journal-title":"Discr. Math"},{"key":"4_CR15","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1016\/0012-365X(88)90191-4","volume":"72","author":"R Chen","year":"1988","unstructured":"R. Chen, X. Guo, and F. Zhang, The z-transformation graphs of perfect matchings of hexagonal system, Discr. Math. Vol. 72 (1988) pp. 405\u2013415.","journal-title":"Discr. Math"},{"issue":"4","key":"4_CR16","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1109\/12.54847","volume":"39","author":"KT Cheng","year":"1990","unstructured":"K.T. Cheng, and V.D. Agrawal, A partial scan method for sequential circuits with feedback, IEEE Transactions on Computers Vol. 39 No. 4 (1990) pp. 544\u2013548.","journal-title":"Ieee Transactions on Computers"},{"key":"4_CR17","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/S0020-0190(96)00193-7","volume":"61","author":"L Lung","year":"1997","unstructured":"Chin Lung Lu, and Chuan Yi Tang, A linear-time algorithm for the weighted feedback vertex problem on interval graphs, Information Processing Letters Vol. 61 (1997) pp. 107\u2013111.","journal-title":"Information Processing Letters"},{"key":"4_CR18","first-page":"233","volume":"4","author":"FA Chudak","year":"1979","unstructured":"F.A. Chudak, M.X. Goemans, D. Hochbaum, and D.P. Williamson, A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs, Operations Research Letters Vol.22 (1998) pp.111\u2013118. Vol. 4 (1979) pp. 233\u2013235.","journal-title":"A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs, Operations Research Letters Vol.22 (1998) pp.111-118"},{"key":"4_CR19","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V Chvatal","year":"1979","unstructured":"V. Chvatal, A greedy heuristic for the set covering problem, Mathematics Of Operations Research Vol. 4 (1979) pp. 233\u2013235.","journal-title":"Mathematics Of Operations Research"},{"key":"4_CR20","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1002\/net.3230260205","volume":"26","author":"SR Coorg","year":"1995","unstructured":"S.R. Coorg, and C.P. Rangan, Feedback vertex set on cocomparability graphs, Networks Vol. 26 (1995) pp. 101\u2013111.","journal-title":"Networks"},{"key":"4_CR21","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0166-218X(88)90086-8","volume":"22","author":"DG Corneil","year":"1988","unstructured":"D.G. Corneil, and J. Fonlupt, The complexity of generalized clique covering, Discr. Appl. Math. Vol. 22 (1988) pp. 109\u2013118.","journal-title":"Discr. Appl. Math"},{"key":"4_CR22","unstructured":"R. Dechter, and J. Pearl, The cycle cutset method for improving search performance in AI, in Proc. of the 3 th IEEE on AI Applications Orlando FL (1987)."},{"key":"4_CR23","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/0004-3702(90)90046-3","volume":"41","author":"R Dechter","year":"1990","unstructured":"R. Dechter, Enhancement schemes for constraint processing: Back-jumping, learning, and cutset decomposition, Artif. Intell. Vol. 41 (1990) pp. 273\u2013312.","journal-title":"Artif. Intell"},{"key":"4_CR24","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1109\/TCS.1985.1085725","volume":"32","author":"J Donald","year":"1995","unstructured":"J. Donald, J. Elwin, R. Hager, and P. Salamon, A bad example for the minimum feedback vertex set problem, IEEE Transactions on Circuits and Systems Vol. 32 (1995) pp. 491\u2013493.","journal-title":"Ieee Transactions on Circuits and Systems"},{"key":"4_CR25","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1137\/S0097539792228228","volume":"24","author":"RG Downey","year":"1995","unstructured":"R.G. Downey, and M.R. Fellows, Fixed-parameter tractability and completeness I: Basic results, SIAM Journal on Computing Vol. 24 (1995) pp. 873\u2013921.","journal-title":"Siam Journal on Computing"},{"key":"4_CR26","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":"P. Erd\u00f6s, and L. Posa, On the maximal number of disjoint circiuts of a graph, Pubbl. Math. Debrecen Vol. 9 (1962) pp. 3\u201312.","journal-title":"Pubbl. Math. Debrecen"},{"key":"4_CR27","unstructured":"G. Even, S. Naor, B. Schieber, and L. Zosin, Approximating minimum subset feedback sets in undirected graphs, with applications, in the Proc. of the 4th Israel Symposium on Theory of Computing and Systems (1996) pp. 78\u201388."},{"key":"4_CR28","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/PL00009191","volume":"20","author":"G Even","year":"1998","unstructured":"G. Even, S. Naor, B. Schieber, and M. Sudan, Approximating minimum feedback sets and multicuts in directed graphs, Algorithmica Vol. 20 (1998) pp. 151\u2013174.","journal-title":"Algorithmica"},{"key":"4_CR29","first-page":"310","volume-title":"And L. Zosin An 8-Approximation Algorithm for the Subset Feedback Vertex Problem, 37th Symp. on Foundations of Comp","author":"G Even","year":"1996","unstructured":"G. Even, J.S. Naor, and L. Zosin An 8-Approximation Algorithm for the Subset Feedback Vertex Problem, 37th Symp. on Foundations of Comp. Sci. ( FOCS ) (1996) pp. 310\u2013319."},{"key":"4_CR30","volume-title":"Fortran subroutines for approximate solution of feedback set problems using GRASP, Manuscript","author":"P Festa","year":"1999","unstructured":"P. Festa, P.M. Pardalos, and M.G.C. Resende, Fortran subroutines for approximate solution of feedback set problems using GRASP, Manuscript, AT & -T Labs Research, Florham Park, NJ (1999)."},{"key":"4_CR31","volume-title":"And G. Reinelt","author":"M Funke","year":"1996","unstructured":"M. Funke, and G. Reinelt, A polyhedral approach to the feedback vertex set problem, Manuscript (1996)."},{"key":"4_CR32","unstructured":"M.R. Carey, and D.S. Johnson, Computers And Intractability \u2014A Guide to the Theory of NP-Completeness, W. H. Freeman, San Francisco, (1979)."},{"key":"4_CR33","first-page":"274276","volume":"7","author":"M.R. Garey","year":"1978","unstructured":"M.R. Garey, and R.E. Tarjan, A linear-time algorithm for finding all feedback vertices, Information Processing Letters Vol.7 (1978) pp. 274276.","journal-title":"Information Processing Letters"},{"issue":"2","key":"4_CR34","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1137\/S0097539793243016","volume":"25","author":"N Garg","year":"1996","unstructured":"N. Garg, V.V. Vazirani, and M. Yannakakis, Approximate max-flow min-(multi) cut theorems and their applications, SIAM Journal on Computing Vol. 25 No. 2 (1996) pp. 235\u2013251.","journal-title":"Siam Journal on Computing"},{"key":"4_CR35","first-page":"91","volume-title":"Proceedings of the 11th Conference on Information Science and Systems","author":"F Gavril","year":"1977","unstructured":"F. Gavril, Some NP-complete problems on graphs, in Proceedings of the 11 th Conference on Information Science and Systems, John Hopkins Univ. Baltimore, Md., (1977) pp. 91\u201395."},{"key":"4_CR36","unstructured":"M.X. Goemans, and D.P. Williamson, Primal-dual approximation algorithms for feedback problems in planar graphs, in Proceedings of the 5 th MPS Conference on Integer Programming and Combinatorial Optimization (IPCO) (1996) pp. 147\u2013161."},{"key":"4_CR37","doi-asserted-by":"publisher","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":"M. Gr\u00f6tschel, L. Lov\u00e2sz, and A. Schrijver, Geometric algorithms and combinatorial optimization, Springer-Verlag, Berlin (1988) pp. 253\u2013254."},{"key":"4_CR38","unstructured":"M. Gr\u00f6tschel, and L. Lov\u00e2sz, Combinatorial optimization: A survey, DIMACS Technical Report 93\u201329 DIMACS Rutgers University (1993)."},{"key":"4_CR39","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF01192587","volume":"6","author":"F Harary","year":"1991","unstructured":"F. Harary, D.J. Klein, and T.P. Zivkovic, Graphical properties of poly-hexes: Perfect matching vector and forcing, J. Math. Chem. Vol. 6 (1991) pp. 295\u2013306.","journal-title":"J. Math. Chem"},{"key":"4_CR40","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1137\/0211045","volume":"3","author":"D Hochbaum","year":"1982","unstructured":"D. Hochbaum, Approximation algorithms for set covering and vertex cover problem, SIAM Journal on Computing Vol.11 No. 3 (1982) pp. 555\u2013556.","journal-title":"Siam Journal on Computing Vol.11"},{"key":"4_CR41","unstructured":"T.C. Hu, Multi-commodity network flows, Operations Research Vol.11 (1963) pp. 344\u2013360."},{"issue":"2","key":"4_CR42","first-page":"1","volume":"20","author":"G Isaak","year":"1995","unstructured":"G. Isaak, Tournaments as feedback arc sets, Electronic Journal of Combinatorics Vol. 20 No. 2 (1995) pp. 1\u201319.","journal-title":"Electronic Journal of Combinatorics"},{"issue":"1","key":"4_CR43","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1137\/0204007","volume":"4","author":"DB Johnson","year":"1975","unstructured":"D.B. Johnson, Finding all the elementary circuits of a directed graph, SIAM J. Computing, Vol. 4, No. 1 (1975) pp. 77\u201384.","journal-title":"Siam J. Computing"},{"key":"4_CR44","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"DS Johnson","year":"1974","unstructured":"D.S. Johnson, Approximation algorithms for combinatorial problems, Journal of Computer and System Science Vol. 9 (1974) pp. 256\u2013278.","journal-title":"Journal of Computer and System Science"},{"key":"4_CR45","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity Of Computer Computations R.E","author":"RM Karp","year":"1972","unstructured":"R.M. Karp, Reducibility among combinatorial problems, Complexity Of Computer Computations R.E. Miller and J.W. Thatcher, Eds., New York: Plenum Press (1972) pp. 85\u2013103."},{"key":"4_CR46","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1109\/TCS.1980.1084814","volume":"27","author":"AK Kevorkian","year":"1980","unstructured":"A.K. Kevorkian, General topological results on the construction of a minimum essential set of a directed graph, IEEE Trans. Circuits and Systems Vol. 27 (1980) pp. 293\u2013304.","journal-title":"Ieee Trans. Circuits and Systems"},{"key":"4_CR47","doi-asserted-by":"publisher","first-page":"516","DOI":"10.1002\/jcc.540080432","volume":"8","author":"DJ Klein","year":"1987","unstructured":"D.J. Klein, and M. Randi\u00e9, Innate degree of freedom of a graph, J. Computat. Chem. Vol. 8 (1987) pp. 516\u2013521.","journal-title":"J. Computat. Chem"},{"key":"4_CR48","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1103\/PhysRevB.43.723","volume":"43","author":"DJ Klein","year":"1991","unstructured":"D.J. Klein, T.P. Zivkovi\u00e9, and R. Valenti, Topological long-range order for resonating-valance-bond structures, Phys. Rev. B Vol. 43A (1991) pp. 723\u2013727.","journal-title":"Phys. Rev. B"},{"key":"4_CR49","unstructured":"A. Kunzmann, and H.J. Wunderlich, An analytical approach to the partial scan problem, J. of Electronic Testing: Theory and Applications Vold (1990) pp. 163\u2013174."},{"key":"4_CR50","first-page":"190","volume-title":"Proc. of the 8th IJCAI","author":"H Kim","year":"1983","unstructured":"H. Kim, and J. Perl, A computational model for combined causal and diagnostic reasoning in inference systems, in Proc. of the 8 th IJCAI, Morgan-Kaufmann, San Mateo, CA, (1983) pp. 190\u2013193."},{"key":"4_CR51","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1111\/j.2517-6161.1988.tb01721.x","volume":"50","author":"SL Lauritzen","year":"1988","unstructured":"S.L. Lauritzen, and D.J. Spiegelhalter, Local computations with probabilities on graphical structures and their application to expert systems (with discussion), J. Roy. Stat. Soc. Ser.B Vol. 50 (1988) pp. 157\u2013224.","journal-title":"J. Roy. Stat. Soc. Ser.B"},{"key":"4_CR52","unstructured":"D. Lee, and S. Reedy, On determining scan flip-flops in partial scan designs, in Proceedings Of International Conference on Computer Aided Design (1990) pp. 322\u2013325."},{"key":"4_CR53","unstructured":"T. Leighton, and S. Rao, An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms, in Proceedings of the 29 th Annual Symposium on Fundations of Computer Science, (1988) pp. 422\u2013431."},{"key":"4_CR54","unstructured":"A. Lempel, and I. Cederbaum, Minimum feedback arc and vertex sets of a directed graph, IEEE Transactions on circuit theory CT-13 (1966) pp. 399\u2013403."},{"key":"4_CR55","doi-asserted-by":"publisher","first-page":"470","DOI":"10.1016\/0196-6774(88)90013-2","volume":"9","author":"H Levy","year":"1988","unstructured":"H. Levy, and L. Lowe, A contraction algorithm for finding small cycle cutsets, Journal Of Algorithm Vol. 9 (1988) pp. 470\u2013493.","journal-title":"Journal Of Algorithm"},{"key":"4_CR56","unstructured":"X.Li, and F. Zhang, Hexagonal systems with forcing edges, Discr. Math. Vol.140 (1995) pp. 253\u2013263"},{"key":"4_CR57","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/0020-0190(94)00133-2","volume":"52","author":"YD Liang","year":"1994","unstructured":"Y.D. Liang, On the feedback vertex set problem in permutation graphs, Information Processing Letters, Vol. 52 (1994) pp. 123\u2013129.","journal-title":"Information Processing Letters"},{"key":"4_CR58","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0012-365X(94)00268-N","volume":"148","author":"J Liu","year":"1996","unstructured":"J. Liu, and C. Zhao, A new bound on the feedback vertex sets in cubic graphs, Discrete Mathematics Vol. 148 (1996) pp. 119\u2013131.","journal-title":"Discrete Mathematics"},{"key":"4_CR59","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1016\/0022-0000(88)90009-8","volume":"37","author":"EL Lloyd","year":"1988","unstructured":"E.L. Lloyd, M.L. Soffa, and C.C. Wang, On locating minimum feedback vertex sets, Journal of Computer and System Sciences Vol. 37 (1988) pp. 292\u2013311.","journal-title":"Journal of Computer and System Sciences"},{"key":"4_CR60","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1112\/jlms\/s2-17.3.369","volume":"17","author":"CL Lucchesi","year":"1978","unstructured":"C.L. Lucchesi, and D.H. Younger, A minimax theorem for directed graphs, J. London Math. Soc. Vol. 17 (1978) pp. 369\u2013374.","journal-title":"J. London Math. Soc"},{"key":"4_CR61","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/S0020-0190(98)00039-8","volume":"66","author":"FL Luccio","year":"1998","unstructured":"F.L. Luccio, Almost exact minimum feedback vertex set in meshes and butterflies, Information Processing Letters Vol. 66 ( 1998, pp. 59\u201364.","journal-title":"Information Processing Letters"},{"key":"4_CR62","unstructured":"C Lund, and M. Yannakakis, On the hardness of approximating minimization problems, Proceedings Of the 25th ACM Symp. On Theory Of Computing (1993) pp. 286\u2013293."},{"key":"4_CR63","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0166-218X(92)90116-R","volume":"39","author":"MV Marathe","year":"1992","unstructured":"M.V. Marathe, C.Pandu Rangan, and R. Ravi, Efficient algorithms for generalized clique covering on interval graphs, Discr. Appl. Math. Vol. 39 (1992) pp. 87\u201393.","journal-title":"Discr. Appl. Math"},{"key":"4_CR64","unstructured":"B. Monien, and R. Schultz, Four approximation algorithms for the feedback vertex set problems, in Proc. of the 7 th Conference on Graph Theoretic Concepts of Computer Science, Hanser-Verlag, Munich (1981) pp. 315\u2013326."},{"key":"4_CR65","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/BF00993315","volume":"7","author":"T Orenstein","year":"1995","unstructured":"T. Orenstein, Z. Kohavi, and I. Pomeranz, An optimal algorithm for cycle breaking in directed graphs, J. of Electronic Testing: Theory and Applications Vol. 7 (1995) pp. 71\u201381.","journal-title":"J. of Electronic Testing: Theory and Applications"},{"key":"4_CR66","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0012-365X(97)00266-5","volume":"190","author":"L Pachter","year":"1998","unstructured":"L. Pachter, and P. Kim, Forcing matchings on square grids, Discr. Math Vol. 190 (1998) pp. 287\u2013294.","journal-title":"Discr. Math"},{"key":"4_CR67","unstructured":"C. Papadimitriou, and M. Yannakakis, Optimization, approximation and complexity classes, in Proc. of the 20th Annual ACM Symp. on Theory of Computing (1988) pp. 251\u2013277."},{"key":"4_CR68","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1023\/A:1009736921890","volume":"2","author":"PM Pardalos","year":"1999","unstructured":"P.M. Pardalos, T. Qian, and M.G.C. Resende, A greedy randomized adaptive search procedure for feedback vertex set, J. Comb. Opt. Vol. 2 (1999) pp. 399\u2013412.","journal-title":"J. Comb. Opt"},{"key":"4_CR69","unstructured":"D. Peleg, Local majority voting, small coalitions, and controlling monopolies in graphs: A review, in Proc. of the 3 th Colloquium on Structural Information and Communication Complexity (1996) pp. 152\u2013169."},{"key":"4_CR70","unstructured":"D. Peleg, Size bounds for dynamic monopolies, in Proc. of the 4th Colloquium on Structural Information and Communication Complexity (1997) Carleton Univ. Press, Ottawa, pp. 165\u2013175."},{"key":"4_CR71","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/0004-3702(86)90072-X","volume":"29","author":"J Perl","year":"1986","unstructured":"J. Perl, Fusion, propagation and structuring in belief networks, Artif. Intell. Vol. 29 (1986) pp. 241\u2013288.","journal-title":"Artif. Intell"},{"key":"4_CR72","unstructured":"T. Qian, Y. Ye, and P.M. Pardalos, A Pseudo-e approximation algorithm for feedback vertex set, Recent Advances in Global Optimization, Floudas, C.A. and Pardalos, P.M., Eds., Kluwer Academic Publishing (1995) pp. 341\u2013351."},{"key":"4_CR73","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/0196-6774(88)90022-3","volume":"9","author":"V Ramachandran","year":"1988","unstructured":"V. Ramachandran, Finding a minimum feedback arc set in reducible flow graphs, Journal of Algorithms Vol. 9 (1988) pp. 299\u2013313.","journal-title":"Journal of Algorithms"},{"key":"4_CR74","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0196-6774(82)90020-7","volume":"3","author":"B Rosen","year":"1982","unstructured":"B. Rosen, Robust linear algorithms for cutsets, Journal of Algorithms Vol. 3 (1982) pp. 205\u2013217.","journal-title":"Journal of Algorithms"},{"key":"4_CR75","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/BF01200760","volume":"15","author":"PD Seymour","year":"1995","unstructured":"P.D. Seymour, Packing directed circuits fractionally, Combinatorica Vol. 15 (1995) pp. 281\u2013288.","journal-title":"Combinatorica"},{"key":"4_CR76","unstructured":"A. Shamir, A linear time algorithm for finding minimum cutsets in reduced graphs, SIAM Journal On Computing Vol.8 No.4 (1979) pp. 645\u2013655."},{"key":"4_CR77","unstructured":"R.D. Shatcher, S.K. Andersen, and P. Szolovits, Global conditioning for probabilistic inference in belief networks, in Proc of the 10 th Conferences on Uncertainty in AI,Seattle, WA (1994) pp. 514-522."},{"key":"4_CR78","volume-title":"The logical design of operating systems","author":"AC Shaw","year":"1974","unstructured":"A.C. Shaw, The logical design of operating systems, Prentice-Hall, Englewood Cliffs, NJ, (1974)."},{"key":"4_CR79","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1016\/0020-0190(79)90144-3","volume":"8","author":"DA Simovici","year":"1979","unstructured":"D.A. Simovici, and G. Grigoras, Even initial feedback vertex set problem is NP-complete, Information Processing Letters Vol. 8 (1979) pp. 64\u201366.","journal-title":"Information Processing Letters"},{"key":"4_CR80","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1109\/TCS.1975.1083961","volume":"1","author":"GW Smith","year":"1975","unstructured":"G.W. Smith, and R.B. Walford, The identification of a minimal feedback vertex set of a directed graph, IEEE Transactions on Circuits and Systems Vol.CAS-22 No. 1, (1975) pp. 9\u201314.","journal-title":"The identification of a minimal feedback vertex set of a directed graph, Ieee Transactions on Circuits and Systems Vol.CAS-22"},{"key":"4_CR81","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1002\/jgt.3190120311","volume":"12","author":"E Speckenmeyer","year":"1988","unstructured":"E. Speckenmeyer, On feedback vertex sets and nonseparating independent sets in cubic graphs, Journal of Graph Theory Vol. 12 (1988) pp. 405\u2013412.","journal-title":"Journal of Graph Theory"},{"key":"4_CR82","first-page":"218","volume":"411","author":"E Speckenmeyer","year":"1989","unstructured":"E. Speckenmeyer, On feedback problems in digraphs, in Lecture Notes in Computer Science, Springer-Verlag Vol. 411 (1989) pp. 218\u2013231.","journal-title":"Springer-verlag"},{"key":"4_CR83","unstructured":"H. Stamm, On feedback problems in a planar digraph, in R. M\u00f6hring ed. Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, Springer-Verlag (1990) Vol. 484 pp. 79\u201389."},{"key":"4_CR84","unstructured":"R.E. Tarjan, Depth first search and linear graph algorithms, SIAM Journal on Computing Vol.1 (1972) pp. 146\u2013160."},{"key":"4_CR85","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1016\/0012-365X(88)90226-9","volume":"72","author":"S Ueno","year":"1988","unstructured":"S. Ueno, Y. Kajitani, and S. Gotoh, On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three, Discrete Mathematics Vol. 72 (1988) pp. 355\u2013360.","journal-title":"Discrete Mathematics"},{"key":"4_CR86","unstructured":"V. Vazirani, Approximation Algorithms, Manuscript, College of Computing, Georgia Institute of Technology."},{"issue":"2","key":"4_CR87","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1145\/3149.3159","volume":"32","author":"C Wang","year":"1985","unstructured":"C. Wang, E. Lloyd, and M. Soffa, Feedback vertex sets and cyclically reducible graphs, Journal of the Association for Computing Machinery Vol. 32 No. 2 (1985) pp. 296\u2013313.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"4_CR88","unstructured":"M. Yannakakis, Node and edge-deletion NP-complete problems, in Proceedings of the 10t h Annual ACM Symposium on Theory of Computing (1978) pp. 253\u2013264."},{"key":"4_CR89","doi-asserted-by":"crossref","first-page":"133137","DOI":"10.1016\/0020-0190(87)90107-4","volume":"24","author":"M. Yannakakis","year":"1987","unstructured":"M. Yannakakis, and F. Gavril, The maximum k-colorable subgraph problem for chordal graphs, Info. Process. Lett Vol.24 (1987) pp. 133137.","journal-title":"Info. Process. Lett"},{"key":"4_CR90","unstructured":"M. Yannakakis, Some open problems in approximation, in Proc. of the second Italian Conference on Algorithm and Complexity, CIAC\u201994 Italy, Feb. (1994) pp. 33\u201339."},{"key":"4_CR91","unstructured":"D.H. Younger, Minimum feedback arc set for a directed graph, IEEE Transactions on Circuit Theory Vol. CT-10 (1963) pp. 238\u2013245."},{"key":"4_CR92","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/0012-365X(90)90165-E","volume":"85","author":"M Zheng","year":"1990","unstructured":"M. Zheng, and X. Lu, On the maximum induced forests of a connected cubic graph without triangles, Discr. Math. Vol. 85 (1990) pp. 89\u201396.","journal-title":"Discr. Math"}],"container-title":["Handbook of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4757-3023-4_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,6]],"date-time":"2024-05-06T09:21:50Z","timestamp":1714987310000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-1-4757-3023-4_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9781441948137","9781475730234"],"references-count":92,"URL":"https:\/\/doi.org\/10.1007\/978-1-4757-3023-4_4","relation":{},"subject":[],"published":{"date-parts":[[1999]]}}}