{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T05:40:42Z","timestamp":1737006042251,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540678236"},{"type":"electronic","value":"9783540449294"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44929-9_15","type":"book-chapter","created":{"date-parts":[[2007,5,5]],"date-time":"2007-05-05T13:20:53Z","timestamp":1178371253000},"page":"186-199","source":"Crossref","is-referenced-by-count":2,"title":["On the Hardness of Approximating Some NP-Optimization Problems Related to Minimum Linear Ordering Problem"],"prefix":"10.1007","author":[{"given":"Sounaka","family":"Mishra","sequence":"first","affiliation":[]},{"given":"Kripasindhu","family":"Sikdar","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,8,24]]},"reference":[{"key":"15_CR1","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1007\/3-540-62592-5_80","volume-title":"Proc. 3rd Italian Conf. on Algorithms and Complexity","author":"P. Alimonti","year":"1997","unstructured":"P. Alimonti and V. Kann. Hardness of approximating problems on cubic graphs. in Proc. 3rd Italian Conf. on Algorithms and Complexity, LNCS-1203, Springer-Verlag (1997) 288\u2013298."},{"key":"15_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(94)00291-P","volume":"150","author":"G. Ausiello","year":"1995","unstructured":"G. Ausiello, P. Crescenzi and M. Protasi. Fundamental Study: Approximate solu-tion of NP optimization problems, Theoretical Computer Science 150 (1995) 1\u201355.","journal-title":"Theoretical Computer Science"},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"V. Bafna, P. Berman and T. Fujito. Constant ratio approximations of feedback vertex sets in weighted undirected graphs, in 6th Annual International Symposium on Algorithms and Computation (1995).","DOI":"10.1007\/BFb0015417"},{"key":"15_CR4","unstructured":"A. Chaudhary and S. Vishwanathan. Approximation algorithms for achromatic number, Proc. 8th Ann. ACM-SIAM Symp. on Discrete Algorithms, ACM-SIAM, (1997) 558\u2013563."},{"key":"15_CR5","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0166-218X(90)90065-K","volume":"27","author":"G. A. Cheston","year":"1990","unstructured":"G. A. Cheston, G. Fricke, S. T. Hedetniemi and D. P. Jacobs. On the computa-tional complexity of upper fractional domination. Discrete Appl. Math., 27 (1990) 195\u2013207.","journal-title":"Discrete Appl. Math."},{"key":"15_CR6","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/0890-5401(91)90025-W","volume":"93","author":"P. Crescenzi","year":"1991","unstructured":"P. Crescenzi and A. Panconesi. Completeness in approximation classes. Informa-tion and Computation, 93 (1991) 241\u2013262.","journal-title":"Informa-tion and Computation"},{"key":"15_CR7","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1007\/BFb0030875","volume-title":"1st. Annu. Int. Conf. on Computing and Combinatorics","author":"P. Crescenzi","year":"1995","unstructured":"P. Crescenzi, V. Kann, R. Silvestri and L. Trevisan. Structures in approximation classes, in 1st. Annu. Int. Conf. on Computing and Combinatorics, LNCS-959, Springer-Verlag, (1995) 539\u2013548."},{"key":"15_CR8","unstructured":"T. Fujito. Personal communication, 1999."},{"key":"15_CR9","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1007\/BF01582009","volume":"33","author":"M. Gr\u00f6tschel","year":"1985","unstructured":"M. Gr\u00f6tschel, M. J:unger and G. Reinelt. On the acyclic subgraph polytope, Math. Programming 33 (1985) 28\u201342.","journal-title":"Math. Programming"},{"key":"15_CR10","doi-asserted-by":"crossref","DOI":"10.21236\/AD0705364","volume-title":"Graph Theory","author":"F. Harary","year":"1969","unstructured":"F. Harary. \u201cGraph Theory\u201d, Addition-Wesley, Reading, MA, 1969."},{"key":"15_CR11","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1002\/jgt.3190070302","volume":"7","author":"F. Harary","year":"1983","unstructured":"F. Harary. Maximum versus minimum invariants for graphs, Jr. of Graph Theory, 7 (1983) 275\u2013284.","journal-title":"Jr. of Graph Theory"},{"key":"15_CR12","doi-asserted-by":"crossref","unstructured":"J. Hastad. Clique is hard to approximate within n1-c, In Proc. 37th IEEE Sympo. on Foundation of Comput. Sci. (1996) 627\u2013636.","DOI":"10.1109\/SFCS.1996.548522"},{"key":"15_CR13","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0020-0190(93)90022-2","volume":"46","author":"M. M. Hald\u00f3rsson","year":"1993","unstructured":"M. M. Hald\u00f3rsson. Approximating the minimum maximal independence number, Info. Proc. Letters, 46 (1993) 169\u2013172.","journal-title":"Info. Proc. Letters"},{"key":"15_CR14","volume-title":"Ph.D. thesis","author":"V. Kann","year":"1992","unstructured":"V. Kann, On the Approximability of NP-complete Optimization Problems, Ph.D. thesis, Dept. of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm, 1992."},{"key":"15_CR15","doi-asserted-by":"crossref","unstructured":"S. Khanna, R. Motwani, M. Sudan and U. Vazirani. On syntactic versus compu-tational views of approximability, in Proc. 35th Ann. IEEE Symp. on Foundations of Computer Science (1994) 819\u2013836.","DOI":"10.1109\/SFCS.1994.365712"},{"key":"15_CR16","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"C. Lund","year":"1994","unstructured":"C. Lund and M. Yannakakis. On the hardness of approximating minimization pro-blems, J, ACM, 41 (1994) 960\u2013981.","journal-title":"J, ACM"},{"key":"15_CR17","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. H. Papadimitriou","year":"1991","unstructured":"C. H. Papadimitriou and M. Yannakakis. Optimization, Approximation, and Com-plexity Classes. J. Comput. System Sci. 43 (1991) 425\u2013440.","journal-title":"J. Comput. System Sci"},{"key":"15_CR18","first-page":"59","volume":"21","author":"K. Peters","year":"1986","unstructured":"K. Peters, R. Laskar and S. T. Hedetniemi. Maximinimal\/Minimaximal connec-tivity in graphs. Ars Combinatoria, 21 (1986) 59\u201370.","journal-title":"Ars Combinatoria"},{"key":"15_CR19","unstructured":"D. F. Manlove. Minimaximal and maximinimal optimization problems: a partial order-based approach, Ph. D. Thesis, University of Glasgow (1998)."},{"key":"15_CR20","unstructured":"S. Mishra and K. Sikdar. On approximate Solutions of Linear Ordering Problems, T. R. No.-5\/98,Stat-Math Unit, Indian Statistical Institute, Calcutta."},{"key":"15_CR21","unstructured":"S. Mishra and K. Sikdar. On the hardness of approximating some NP-optimization problems related to minimum linear ordering problem, T. R. No.-7\/99,Stat-Math Unit, Indian Statistical Institute, Calcutta."},{"key":"15_CR22","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. Kajtani and S. Gotoh. On the nonseparating independent set problem and feedback set problem for graphs with no vertex exceeding three, Disc. Math., 72 (1988) 355\u2013360.","journal-title":"Disc. Math."}],"container-title":["Lecture Notes in Computer Science","Theoretical Computer Science: Exploring New Frontiers of Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44929-9_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T02:15:20Z","timestamp":1736993720000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44929-9_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540678236","9783540449294"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-44929-9_15","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}