{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:44:34Z","timestamp":1759063474268},"reference-count":23,"publisher":"Elsevier BV","issue":"3","license":[{"start":{"date-parts":[[2003,5,1]],"date-time":"2003-05-01T00:00:00Z","timestamp":1051747200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information Processing Letters"],"published-print":{"date-parts":[[2003,5]]},"DOI":"10.1016\/s0020-0190(02)00491-x","type":"journal-article","created":{"date-parts":[[2003,4,7]],"date-time":"2003-04-07T17:25:26Z","timestamp":1049736326000},"page":"129-136","source":"Crossref","is-referenced-by-count":33,"title":["Combinatorial algorithms for feedback problems in directed graphs"],"prefix":"10.1016","volume":"86","author":[{"given":"Camil","family":"Demetrescu","sequence":"first","affiliation":[]},{"given":"Irene","family":"Finocchi","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0020-0190(02)00491-X_BIB001","series-title":"Proceedings of the 6th International Symposium on Algorithms and Computation (ISAAC'95)","first-page":"142","article-title":"Constant ratio approximations of the weighted feedback vertex set problem","volume":"1004","author":"Bafna","year":"1995"},{"key":"10.1016\/S0020-0190(02)00491-X_BIB002","series-title":"Proceedings of the 1st Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'98)","first-page":"49","article-title":"One for the price of two: A unified approach for approximating covering problems","author":"Bar-Yehuda","year":"1998"},{"key":"10.1016\/S0020-0190(02)00491-X_BIB003","first-page":"27","article-title":"A local-ratio theorem for approximating the weighted vertex cover problem","volume":"25","author":"Bar-Yehuda","year":"1985","journal-title":"Ann. Discrete Math."},{"issue":"4","key":"10.1016\/S0020-0190(02)00491-X_BIB004","doi-asserted-by":"crossref","first-page":"942","DOI":"10.1137\/S0097539796305109","article-title":"Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and Bayesian inference","volume":"27","author":"Bar-Yehuda","year":"1998","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0020-0190(02)00491-X_BIB005","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/0004-3702(95)00004-6","article-title":"Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the feedback vertex set problem","volume":"83","author":"Becker","year":"1996","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S0020-0190(02)00491-X_BIB006","series-title":"Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms","first-page":"236","article-title":"Approximation algorithms for the maximum acyclic subgraph problem","author":"Berger","year":"1990"},{"key":"10.1016\/S0020-0190(02)00491-X_BIB007","series-title":"Proceedings of the 2nd International Workshop on Algorithm Engineering and Experiments (ALENEX'00)","first-page":"171","article-title":"Break the \u201cright\u201d cycles and get the \u201cbest\u201d drawing","author":"Demetrescu","year":"2000"},{"key":"10.1016\/S0020-0190(02)00491-X_BIB008","series-title":"Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS'00)","first-page":"381","article-title":"Fully dynamic transitive closure: Breaking through the O(n2) barrier","author":"Demetrescu","year":"2000"},{"key":"10.1016\/S0020-0190(02)00491-X_BIB009","first-page":"15","article-title":"A new heuristic for the feedback arc set problem","volume":"12","author":"Eades","year":"1995","journal-title":"Australian J. Combin."},{"issue":"6","key":"10.1016\/S0020-0190(02)00491-X_BIB010","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1016\/0020-0190(93)90079-O","article-title":"A fast and effective heuristic for the feedback arc set problem","volume":"47","author":"Eades","year":"1993","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0020-0190(02)00491-X_BIB011","series-title":"Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science","first-page":"62","article-title":"Divide-and-conquer approximation algorithms via spreading metrics","author":"Even","year":"1995"},{"key":"10.1016\/S0020-0190(02)00491-X_BIB012","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/net.3230200102","article-title":"Exact and heuristic algorithms for the weighted feedback arc set problem: A special case of the skew-symmetric quadratic assignment problem","volume":"20","author":"Flood","year":"1990","journal-title":"Networks"},{"key":"10.1016\/S0020-0190(02)00491-X_BIB013","series-title":"Computers and Intractability: A Guide to Theory of NP-completeness","author":"Garey","year":"1979"},{"key":"10.1016\/S0020-0190(02)00491-X_BIB014","series-title":"Proceedings of the 11th Conference on Information Sciences and Systems","first-page":"91","article-title":"Some NP-complete problems on graphs","author":"Gavril","year":"1977"},{"key":"10.1016\/S0020-0190(02)00491-X_BIB015","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0020-0190(94)00086-7","article-title":"Approximations for the maximum acyclic subgraph problem","volume":"51","author":"Hassin","year":"1994","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0020-0190(02)00491-X_BIB016","series-title":"Approximations Algorithms for NP-Hard Problems","year":"1997"},{"key":"10.1016\/S0020-0190(02)00491-X_BIB017","unstructured":"V. Kann, On the approximability of NP-complete optimization problems, PhD thesis, Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm, 1992"},{"key":"10.1016\/S0020-0190(02)00491-X_BIB018","series-title":"Complexity of Computer Computations","first-page":"85","article-title":"Reducibility among combinatorial problems","author":"Karp","year":"1972"},{"issue":"4","key":"10.1016\/S0020-0190(02)00491-X_BIB019","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1109\/TCT.1966.1082620","article-title":"Minimum feedback arc and vertex sets of a directed graph","volume":"13","author":"Lempel","year":"1966","journal-title":"IEEE Trans. Circuit Theory"},{"key":"10.1016\/S0020-0190(02)00491-X_BIB020","unstructured":"C.L. Lucchesi, A minimax equality for directed graphs, PhD thesis, University of Waterloo, 1966"},{"key":"10.1016\/S0020-0190(02)00491-X_BIB021","unstructured":"B. Schwikowski and E. Speckenmeyer, On computing all minimal solutions for feedback problems, Technical report, Universit\u00e4t zu K\u00f6ln, 1997"},{"key":"10.1016\/S0020-0190(02)00491-X_BIB022","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/BF01200760","article-title":"Packing directed circuits fractionally","volume":"15","author":"Seymour","year":"1995","journal-title":"Combinatorica"},{"issue":"2","key":"10.1016\/S0020-0190(02)00491-X_BIB023","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1109\/TSMC.1981.4308636","article-title":"Methods for visual understanding of hierarchical system structures","volume":"11","author":"Sugiyama","year":"1981","journal-title":"IEEE Trans. Syst. Man Cybern."}],"container-title":["Information Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S002001900200491X?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S002001900200491X?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,3,24]],"date-time":"2019-03-24T17:29:30Z","timestamp":1553448570000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S002001900200491X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,5]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2003,5]]}},"alternative-id":["S002001900200491X"],"URL":"https:\/\/doi.org\/10.1016\/s0020-0190(02)00491-x","relation":{},"ISSN":["0020-0190"],"issn-type":[{"value":"0020-0190","type":"print"}],"subject":[],"published":{"date-parts":[[2003,5]]}}}