{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:37:02Z","timestamp":1725561422654},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540206958"},{"type":"electronic","value":"9783540245872"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-24587-2_17","type":"book-chapter","created":{"date-parts":[[2010,7,29]],"date-time":"2010-07-29T08:59:19Z","timestamp":1280393959000},"page":"148-157","source":"Crossref","is-referenced-by-count":6,"title":["Labeled Search Trees and Amortized Analysis: Improved Upper Bounds for NP-Hard Problems"],"prefix":"10.1007","author":[{"given":"Jianer","family":"Chen","sequence":"first","affiliation":[]},{"given":"Iyad A.","family":"Kanj","sequence":"additional","affiliation":[]},{"given":"Ge","family":"Xia","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"17_CR1","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/S0020-0190(97)00213-5","volume":"65","author":"R. Balasubramanian","year":"1998","unstructured":"Balasubramanian, R., Fellows, M.R., Raman, V.: An improved fixed parameter algorithm for vertex cover. Inform. Process. Lett.\u00a065, 163\u2013168 (1998)","journal-title":"Inform. Process. Lett."},{"key":"17_CR2","unstructured":"Beigel, R.: Finding maximum independent sets in sparse and general graphs. In: Proc. 10th ACM-SIAM Symp. on Discrete Algorithms (SODA 1999), pp. 856\u2013857 (1999)"},{"key":"17_CR3","doi-asserted-by":"publisher","first-page":"560","DOI":"10.1137\/0222038","volume":"22","author":"J.F. Buss","year":"1993","unstructured":"Buss, J.F., Goldsmith, J.: Nondeterminism within P. SIAM J. Comput.\u00a022, 560\u2013572 (1993)","journal-title":"SIAM J. Comput."},{"key":"17_CR4","unstructured":"Cai, L., Juedes, D.: On the existence of subexponential-time parameterized algorithms, Available at http:\/\/www.cs.uga.edu\/~cai\/"},{"key":"17_CR5","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1006\/jagm.2001.1186","volume":"41","author":"J. Chen","year":"2001","unstructured":"Chen, J., Kanj, I.A., Jia, W.: Vertex cover: further observations and further improvements. J. Algorithms\u00a041, 280\u2013301 (2001)","journal-title":"J. Algorithms"},{"key":"17_CR6","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1002\/1097-0037(200007)35:4<253::AID-NET3>3.0.CO;2-K","volume":"35","author":"J. Chen","year":"2000","unstructured":"Chen, J., Liu, L., Jia, W.: Improvement on vertex cover for low-degree graphs. Networks\u00a035, 253\u2013259 (2000)","journal-title":"Networks"},{"key":"17_CR7","unstructured":"DIMACS Workshop on Faster Exact Algorithms for NP-hard problems, Princeton, NJ (2000)"},{"key":"17_CR8","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/978-1-4612-2566-9_7","volume-title":"Feasible Mathematics II","author":"R. Downey","year":"1995","unstructured":"Downey, R., Fellows, M.: Parameterized computational feasibility. In: Clote, P., Remmel, J. (eds.) Feasible Mathematics II, pp. 219\u2013244. Birkh\u00e4user, Boston (1995)"},{"key":"17_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R. Downey","year":"1999","unstructured":"Downey, R., Fellows, M.: Parameterized Complexity. Springer, New York (1999)"},{"key":"17_CR10","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/BF02241270","volume":"44","author":"P. Hansen","year":"1990","unstructured":"Hansen, P., Jaumard, B.: Algorithms for the maximum satisfiability problem. Computing\u00a044, 279\u2013303 (1990)","journal-title":"Computing"},{"issue":"4","key":"17_CR11","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. System Sci.\u00a063(4), 512\u2013530 (2001)","journal-title":"J. Comput. System Sci."},{"key":"17_CR12","doi-asserted-by":"publisher","first-page":"847","DOI":"10.1109\/TC.1986.1676847","volume":"35","author":"T. Jian","year":"1986","unstructured":"Jian, T.: An O(20.304n ) algorithm for solving the maximum independent set problem. IEEE Trans. Comput.\u00a035, 847\u2013851 (1986)","journal-title":"IEEE Trans. Comput."},{"key":"17_CR13","unstructured":"Johnson, D., Szegedy, M.: What are the least tractable instances of max. independent set? In: Proc. 10th ACM-SIAM Symp. on Discrete Algorithms, pp. 927\u2013928 (1999)"},{"key":"17_CR14","doi-asserted-by":"crossref","unstructured":"Johnson, D.S., Tricks, M.A. (eds.): Cliques, Coloring and Satisfiability, Second DIMACS Implementation Challenges, DIMACS Series on Discrete Mathematics and Theoretical Computer Science 26, AMS, Providence (1996)","DOI":"10.1090\/dimacs\/026"},{"key":"17_CR15","unstructured":"Kanj, I.A.: Vertex Cover: Exact and Approximate Algorithms and Applications, Ph.D. Dissertation, Dept. of Computer Science, Texas A&M University, College Station, Texas (2001)"},{"key":"17_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1007\/3-540-49116-3_53","volume-title":"STACS 99","author":"R. Niedermeier","year":"1999","unstructured":"Niedermeier, R., Rossmanith, P.: Upper bounds for vertex cover further improved. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol.\u00a01563, pp. 561\u2013570. Springer, Heidelberg (1999)"},{"key":"17_CR17","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0020-0190(00)00004-1","volume":"73","author":"R. Niedermeier","year":"2000","unstructured":"Niedermeier, R., Rossmanith, P.: A general method to speed up fixedparameter- tractable algorithms. Inform. Process. Lett.\u00a073, 125\u2013129 (2000)","journal-title":"Inform. Process. Lett."},{"key":"17_CR18","first-page":"425","volume":"6","author":"J.M. Robson","year":"1977","unstructured":"Robson, J.M.: Algorithms for maximum independent set. J. Algorithms\u00a06, 425\u2013440 (1977)","journal-title":"J. Algorithms"},{"key":"17_CR19","unstructured":"Stege, U., Fellows, M.: An improved fixed-parameter-tractable algorithm for vertex cover, Technical Report 318, Department of Computer Science, ETH Zurich (April 1999)"},{"key":"17_CR20","first-page":"537","volume":"7","author":"R.E. Tarjan","year":"1986","unstructured":"Tarjan, R.E., Trojanowski, A.E.: Finding a maximum independent set. SIAM J. Comput.\u00a07, 537\u2013546 (1986)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24587-2_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T23:56:11Z","timestamp":1559346971000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24587-2_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540206958","9783540245872"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24587-2_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}