{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T13:40:29Z","timestamp":1772372429330,"version":"3.50.1"},"reference-count":33,"publisher":"EDP Sciences","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"published-print":{"date-parts":[[2001,5]]},"DOI":"10.1051\/ita:2001121","type":"journal-article","created":{"date-parts":[[2003,11,14]],"date-time":"2003-11-14T15:10:28Z","timestamp":1068822628000},"page":"287-309","source":"Crossref","is-referenced-by-count":6,"title":["On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem"],"prefix":"10.1051","volume":"35","author":[{"given":"Sounaka","family":"Mishra","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kripasindhu","family":"Sikdar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2002,4,15]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"P. Alimonti and V. Kann, Hardness of approximating problems on cubic graphs, inProc. 3rd Italian Conf. on Algorithms and Complexity. Springer-Verlag,Lecture Notes in Comput. Sci.1203(1997) 288-298.","DOI":"10.1007\/3-540-62592-5_80"},{"key":"R2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(94)00291-P","volume":"150","author":"Ausiello","year":"1995","journal-title":"Theoret. Comput. Sci."},{"key":"R3","doi-asserted-by":"crossref","unstructured":"G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela and M. Protasi,Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer-Verlag, Berlin Heidelberg (1999).","DOI":"10.1007\/978-3-642-58412-1"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"V. Bafna, P. Berman and T. Fujito, Constant ratio approximations of feedback vertex sets in weighted undirected graphs, in6th Annual International Symposium on Algorithms and Computation(1995).","DOI":"10.1007\/BFb0015417"},{"key":"R5","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/S0166-218X(97)00125-X","volume":"82","author":"Brandst\u00e4dt","year":"1998","journal-title":"Discrete Appl. Math."},{"key":"R6","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0304-3975(87)90128-9","volume":"54","author":"Brandst\u00e4dt","year":"1987","journal-title":"Theoret. Comput. Sci."},{"key":"R7","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/BF00249646","volume":"6","author":"Chanas","year":"1996","journal-title":"Comput. Optim. Appl."},{"key":"R8","doi-asserted-by":"crossref","first-page":"1671","DOI":"10.1137\/S0097539792238431","volume":"27","author":"Chang","year":"1998","journal-title":"SIAM J. Comput."},{"key":"R9","unstructured":"A. Chaudhary and S. Vishwanathan, Approximation algorithms for achromatic number, inProc. 8th Ann. ACM-SIAM Symp. on Discrete Algorithms. ACM-SIAM (1997) 558-563."},{"key":"R10","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0166-218X(90)90065-K","volume":"27","author":"Cheston","year":"1990","journal-title":"Discrete Appl. Math."},{"key":"R11","doi-asserted-by":"crossref","unstructured":"P. Crescenzi, V. Kann, R. Silvestri and L. Trevisan, Structures in approximation classes, in1st. Annu. Int. Conf. on Computing and Combinatorics. Springer-Verlag,Lecture Notes in Comput. Sci.959(1995) 539-548.","DOI":"10.1007\/BFb0030875"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"U. Feige and J. Kilian, Zero knowledge and the chromatic number.Proc. Comp. Complexity(1996).","DOI":"10.1109\/CCC.1996.507690"},{"key":"R13","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1016\/0167-6377(82)90015-3","volume":"1","author":"Fraber","year":"1982","journal-title":"Oper. Res. Lett."},{"key":"R14","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(85)90001-X","volume":"6","author":"Fraber","year":"1985","journal-title":"J. Algorithms"},{"key":"R15","unstructured":"T. Fujito, Personal communication (1999)."},{"key":"R16","doi-asserted-by":"crossref","first-page":"1195","DOI":"10.1287\/opre.32.6.1195","volume":"32","author":"Gr\u00f6tschel","year":"1984","journal-title":"Oper. Res."},{"key":"R17","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1007\/BF01582009","volume":"33","author":"Gr\u00f6tschel","year":"1985","journal-title":"Math. Programming"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad, Clique is hard to approximate withinn1-\u03b5, inProc. 37th IEEE Sympo. on Foundation of Comput. Sci.(1996) 627-636.","DOI":"10.1109\/SFCS.1996.548522"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"F. Harary,Graph Theory. Addition-Wesley, Reading, MA (1969).","DOI":"10.21236\/AD0705364"},{"key":"R20","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1002\/jgt.3190070302","volume":"7","author":"Harary","year":"1983","journal-title":"J. Graph Theory"},{"key":"R21","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1016\/S0021-9800(70)80072-2","volume":"8","author":"Harary","year":"1970","journal-title":"J. Combin. Theory"},{"key":"R22","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0020-0190(93)90022-2","volume":"46","author":"Halld\u00f3rsson","year":"1993","journal-title":"Inform. Process. Lett."},{"key":"R23","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/0020-0190(91)90188-N","volume":"37","author":"Irving","year":"1991","journal-title":"Inform. Process. Lett."},{"key":"R24","unstructured":"V. Kann,On the Approximability of NP-complete Optimization Problems, Ph.D. Thesis. Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm (1992)."},{"key":"R25","first-page":"317","volume":"1","author":"Kann","year":"1994","journal-title":"Nordic J. Comput."},{"key":"R26","doi-asserted-by":"crossref","unstructured":"S. Khanna, R. Motwani, M. Sudan and U. Vazirani, On syntacticversuscomputational views of approximability, inProc. 35th Ann. IEEE Symp. on Foundations of Computer Science(1994) 819-836.","DOI":"10.1109\/SFCS.1994.365712"},{"key":"R27","doi-asserted-by":"crossref","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"Lund","year":"1994","journal-title":"J. ACM"},{"key":"R28","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"Papadimitriou","year":"1991","journal-title":"J. Comput. System Sci."},{"key":"R29","first-page":"59","volume":"21","author":"Peters","year":"1986","journal-title":"Ars Combinatoria"},{"key":"R30","unstructured":"D.F. Manlove,Minimaximal and maximinimal optimization problems: A partial order-based approach, Ph.D. Thesis. University of Glasgow (1998)."},{"key":"R31","doi-asserted-by":"crossref","unstructured":"S. Mishra and K. Sikdar, On approximation solutions of linear ordering and related NP-Optimization problems on graphs (Extended Abstract),Electronic Notes in Discrete Mathematics, Vol. 8, edited by H. Broersma, U. Faigle, J. Hurink and S. Pickl. Elsevier Science Publishers (2001), Full version submitted for publication.","DOI":"10.1016\/S1571-0653(05)80081-2"},{"key":"R32","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1007\/3-540-44929-9_15","volume":"1872","author":"Mishra","year":"2000","journal-title":"Lecture Notes in Comput. Sci."},{"key":"R33","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1016\/0012-365X(88)90226-9","volume":"72","author":"Ueno","year":"1988","journal-title":"Discrete Math."}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita:2001121\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,14]],"date-time":"2024-12-14T11:00:56Z","timestamp":1734174056000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita:2001121"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,5]]},"references-count":33,"journal-issue":{"issue":"3"},"alternative-id":["ita0104"],"URL":"https:\/\/doi.org\/10.1051\/ita:2001121","relation":{},"ISSN":["0988-3754","1290-385X"],"issn-type":[{"value":"0988-3754","type":"print"},{"value":"1290-385X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2001,5]]}}}