{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:17:59Z","timestamp":1759637879475,"version":"3.40.4"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2014,9,1]],"date-time":"2014-09-01T00:00:00Z","timestamp":1409529600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J. Comput. Sci. Technol."],"published-print":{"date-parts":[[2014,9]]},"DOI":"10.1007\/s11390-014-1474-1","type":"journal-article","created":{"date-parts":[[2014,9,21]],"date-time":"2014-09-21T09:42:35Z","timestamp":1411292555000},"page":"870-878","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["On Unknown Small Subsets and Implicit Measures: New Techniques for Parameterized Algorithms"],"prefix":"10.1007","volume":"29","author":[{"given":"Jianer","family":"Chen","sequence":"first","affiliation":[]},{"given":"Qi-Long","family":"Feng","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,9,12]]},"reference":[{"key":"1474_CR1","unstructured":"Garey M R, Johnson D S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York, W. H. Freeman and Company, 1979."},{"key":"1474_CR2","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/j.tcs.2013.06.008","volume":"518","author":"W Luo","year":"2014","unstructured":"Luo W, Wang J, Guo J, Chen J. Parameterized complexity of Max-lifetime Target Coverage in wireless sensor networks. Theoretical Computer Science, 2014, 518: 32\u201341.","journal-title":"Theoretical Computer Science"},{"key":"1474_CR3","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/j.tcs.2013.06.011","volume":"511","author":"J Wang","year":"2013","unstructured":"Wang J, Luo W, Feng Q, Guo J, Chen J. Improved linear problem kernel for planar connected dominating set. Theoretical Computer Science, 2013, 511: 2\u201312.","journal-title":"Theoretical Computer Science"},{"key":"1474_CR4","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1016\/j.tcs.2012.02.040","volume":"508","author":"J Wang","year":"2013","unstructured":"Wang J, Luo W, Feng Q, Guo J. Parameterized complexity of Min-power multicast problems in wireless ad hoc networks. Theoretical Computer Science, 2013, 508: 16\u201325.","journal-title":"Theoretical Computer Science"},{"key":"1474_CR5","doi-asserted-by":"crossref","unstructured":"Wang J, Tan P, Yao J, Feng Q, Chen J. On the minimum link-length rectilinear spanning path problem: Complexity and algorithms. IEEE Transactions on Computers, doi.ieeecomputersociety.org\/ 10.1109\/TC.2013.163 , 2013 (preprint).","DOI":"10.1109\/TC.2013.163"},{"key":"1474_CR6","doi-asserted-by":"crossref","unstructured":"Ausiello G, Crescenzi P, Gambosi G, Kann V, Marchetti-Spaccamela A, Protasi M. Complexity and Approximation\u2014Combinatorial Optimization Problems and Their Approximability Properties. Springer Verlag, 1999.","DOI":"10.1007\/978-3-642-58412-1"},{"key":"1474_CR7","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R Motwani","year":"1995","unstructured":"Motwani R, Raghavan P. Randomized Algorithms. New York: Cambridge University Press, 1995."},{"key":"1474_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04131-4","volume-title":"How to Solve It: Modern Heuristics","author":"Z Michalewicz","year":"2000","unstructured":"Michalewicz Z, Fogel D B. How to Solve It: Modern Heuristics. Berlin: Springer-Verlag, 2000."},{"key":"1474_CR9","unstructured":"Roth-Korostensky C. Algorithms for building multiple sequence alignments and evolutionary trees [Ph.D. Thesis]. No. 13550, ETH Z\u00f6urich, 2000."},{"key":"1474_CR10","unstructured":"Stege U. Resolving conflicts from problems in computational biology [Ph.D. Thesis]. No. 13364, ETH Z\u00f6urich, 2000."},{"key":"1474_CR11","doi-asserted-by":"crossref","unstructured":"Chen J, Kanj I A, Jia W. Vertex cover: Further observations and further improvements. In Proc. Workshop on Graph-Theoretic Concepts in Computer Science-WG, Jun. 1999, pp.313\u2013324.","DOI":"10.1007\/3-540-46784-X_30"},{"key":"1474_CR12","doi-asserted-by":"crossref","unstructured":"Chen J, Kanj I A, Xia G. Improved upper bounds for vertex cover. Theoretical Computer Science, 2010, 411(40\/41\/42): 3736\u20133756.","DOI":"10.1016\/j.tcs.2010.06.026"},{"issue":"4","key":"1474_CR13","doi-asserted-by":"crossref","first-page":"691","DOI":"10.1016\/S0022-0000(03)00075-8","volume":"67","author":"J Cheetham","year":"2003","unstructured":"Cheetham J, Dehne F, Rau-Chaplin A, Stege U, Taillon P J. Solving large FPT problems on coarse-granined parallel machines. Journal of Computer and System Sciences, 2003, 67(4): 691\u2013706.","journal-title":"Journal of Computer and System Sciences"},{"key":"1474_CR14","doi-asserted-by":"crossref","unstructured":"Lichtenstein O, Pnueli A. Checking that finite state concurrent programs satisfy their linear specification. In Proc. the 12th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, Jan. 1985, pp.97\u2013107.","DOI":"10.1145\/318593.318622"},{"issue":"4","key":"1474_CR15","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1017\/S0956796800001143","volume":"4","author":"F Henglein","year":"1994","unstructured":"Henglein F, Mairson H G. The complexity of type inference for higher-order typed lambda calculi. Journal of Functional Programming, 1994, 4(4): 435\u2013477.","journal-title":"Journal of Functional Programming"},{"issue":"4","key":"1474_CR16","doi-asserted-by":"crossref","first-page":"833","DOI":"10.1016\/j.jcss.2003.09.003","volume":"67","author":"J Chen","year":"2003","unstructured":"Chen J, Kanj I A. Constrained minimum vertex cover in bipartite graphs: Complexity and parameterized algorithms. Journal of Computer and System Sciences, 2003, 67(4): 833\u2013847.","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"1474_CR17","doi-asserted-by":"crossref","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon N, Yuster R, Zwick U. Color-coding. Journal of the ACM, 1995, 42(4): 844\u2013856.","journal-title":"Journal of the ACM"},{"issue":"1","key":"1474_CR18","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/j.cosrev.2008.02.004","volume":"2","author":"F Dorn","year":"2008","unstructured":"Dorn F, Fomin F V, Thilikos D M. Subexponential parameterized algorithms. Computer Science Review, 2008, 2(1): 29\u201339.","journal-title":"Computer Science Review"},{"key":"1474_CR19","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. New York: Springer-Verlag, 1999."},{"key":"1474_CR20","doi-asserted-by":"crossref","unstructured":"Niedermeier R. Invitation to Fixed-Parameter Algorithms. Oxford University Press, 2006.","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"issue":"4","key":"1474_CR21","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/j.orl.2003.10.009","volume":"32","author":"B Reed","year":"2004","unstructured":"Reed B, Smith K, Vetta A. Finding odd cycle transversals. Operations Research Letters, 2004, 32(4): 299\u2013301.","journal-title":"Operations Research Letters"},{"issue":"20","key":"1474_CR22","doi-asserted-by":"crossref","first-page":"11394","DOI":"10.1073\/pnas.1534710100","volume":"100","author":"BP Kelley","year":"2003","unstructured":"Kelley B P, Sharan R, Karp R M, Sittler T, Root D E, Stock-well B R, Ideker T. Conserved pathways within bacteria and yeast as revealed by global protein network alignment. Proc. Natl. Acad. Sci., 2003, 100(20): 11394\u201311399.","journal-title":"Proc. Natl. Acad. Sci."},{"issue":"6","key":"1474_CR23","doi-asserted-by":"crossref","first-page":"2526","DOI":"10.1137\/080716475","volume":"38","author":"J Chen","year":"2009","unstructured":"Chen J, Kneis J, Lu S, Molle D, Richter S, Rossmanith P, Sze S H, Zhang F. Randomized divide-and-conquer: Improved path, matching, and packing algorithms. SIAM J. Comput., 2009, 38(6): 2526\u20132547.","journal-title":"SIAM J. Comput."},{"issue":"4","key":"1474_CR24","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1007\/s00453-008-9206-y","volume":"54","author":"J Chen","year":"2009","unstructured":"Chen J, Lu S. Improved parameterized set splitting algorithms: A probabilistic approach. Algorithmica, 2009, 54(4): 472\u2013489.","journal-title":"Algorithmica"},{"issue":"3","key":"1474_CR25","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1137\/0212040","volume":"12","author":"DG Kirkpatrick","year":"1983","unstructured":"Kirkpatrick D G, Hell P. On the complexity of general graph factor problems. SIAM Journal on Computing, 1983, 12(3): 601\u2013609.","journal-title":"SIAM Journal on Computing"},{"key":"1474_CR26","doi-asserted-by":"crossref","unstructured":"Feng Q, Wang J, Chen J. Matching and P 2-Packing: Weighted versions. In Proc. the 17th COCOON, Aug. 2011, pp.343\u2013353.","DOI":"10.1007\/978-3-642-22685-4_31"},{"key":"1474_CR27","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/j.tcs.2013.12.011","volume":"522","author":"Q Feng","year":"2014","unstructured":"Feng Q, Wang J, Chen J. Matching and weighted P2-Packing: Algorithms and kernels. Theoretical Computer Science, 2014, 522: 85\u201394.","journal-title":"Theoretical Computer Science"},{"key":"1474_CR28","doi-asserted-by":"crossref","unstructured":"Feng Q, Wang J, Li S, Chen J. Random methods for parameterized problems. In Proc. the 19th COCOON, Jun. 2013, pp.89-100.","DOI":"10.1007\/978-3-642-38768-5_10"},{"key":"1474_CR29","doi-asserted-by":"crossref","unstructured":"Feng Q, Wang J, Li S, Chen J. Randomized parameterized algorithms for P2-Packing and Co-Path Packing problems. Journal of Combinatorial Optimization, 2014. (to be appeared)","DOI":"10.1007\/s10878-013-9691-z"},{"key":"1474_CR30","unstructured":"Chen J, Lu S, Sze S H, Zhang F. Improved algorithms for path, matching, and packing problems. In Proc. the 18th Annual ACM-SIAM SODA, Jan. 2007, pp.298\u2013307."},{"key":"1474_CR31","doi-asserted-by":"crossref","unstructured":"Naor M, Schulman L, Srinivasan A. Splitters and near-optimal derandomization. In Proc. the 36th Annual Symposium on FOCS, Oct. 1995, pp.182\u2013193.","DOI":"10.1109\/SFCS.1995.492475"},{"key":"1474_CR32","doi-asserted-by":"crossref","unstructured":"Kneis J, M\u00f6olle D, Richter S, Rossmanith P. Divide-and-color. In Proc. the 32nd Int. Workshop WG, Jun. 2006, pp.58\u201367.","DOI":"10.1007\/11917496_6"},{"issue":"23","key":"1474_CR33","doi-asserted-by":"crossref","first-page":"2503","DOI":"10.1016\/j.tcs.2010.10.042","volume":"412","author":"J Chen","year":"2011","unstructured":"Chen J, Feng Q, Liu Y, Lu S, Wang J. Improved deterministic algorithms for weighted matching and packing problems. Theoretical Computer Science, 2011, 412(23): 2503\u20132512.","journal-title":"Theoretical Computer Science"},{"key":"1474_CR34","doi-asserted-by":"crossref","unstructured":"Chen J, Liu Y, Lu S, Sze S H, Zhang F. Iterative expansion and color coding: An improved algorithm for 3D-matching. ACM Transactions on Algorithms, 2012, 8(1): Article No.6.","DOI":"10.1145\/2071379.2071385"},{"issue":"18","key":"1474_CR35","doi-asserted-by":"crossref","first-page":"1745","DOI":"10.1016\/j.tcs.2010.12.048","volume":"412","author":"J Wang","year":"2011","unstructured":"Wang J, Feng Q, Chen J. An O*(3:533k )-time parameterized algorithm for the 3-set packing problem. Theoretical Computer Science, 2011, 412(18): 1745\u20131753.","journal-title":"Theoretical Computer Science"},{"issue":"7","key":"1474_CR36","doi-asserted-by":"crossref","first-page":"1188","DOI":"10.1016\/j.jcss.2008.05.002","volume":"74","author":"J Chen","year":"2008","unstructured":"Chen J, Fomin F, Liu Y, Lu S, Villanger Y. Improved algorithms for the feedback vertex set problems. Journal of Computer and System Sciences, 2008, 74(7): 1188\u20131198.","journal-title":"Journal of Computer and System Sciences"},{"issue":"11","key":"1474_CR37","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00453-007-9130-6","volume":"55","author":"J Chen","year":"2009","unstructured":"Chen J, Liu Y, Lu S. An improved parameterized algorithm for the minimum node multiway cut problem. Algorithmica, 2009, 55(11): 1\u201313.","journal-title":"Algorithmica"},{"key":"1474_CR38","doi-asserted-by":"crossref","unstructured":"Chen J, Kanj I A. On approximating minimum vertex cover for graphs with perfect matching. Theoretical Computer Science, 2005, 337(1\/2\/3): 305\u2013318.","DOI":"10.1016\/j.tcs.2004.12.034"},{"issue":"2","key":"1474_CR39","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1006\/jagm.1998.0996","volume":"31","author":"M Mahajan","year":"1999","unstructured":"Mahajan M, Raman V. Parametrizing above guaranteed values: MaxSat and MaxCut. J. Algorithms, 1999, 31(2): 335\u2013354.","journal-title":"J. Algorithms"},{"key":"1474_CR40","doi-asserted-by":"crossref","unstructured":"Mahajan M, Raman V, Sikdar S. Parameterizing MAX SNP problems above guaranteed values. In Proc. the 2nd Int. Workshop IWPEC, Sept. 2006, pp.38\u201349.","DOI":"10.1007\/11847250_4"},{"issue":"2","key":"1474_CR41","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/j.jcss.2008.08.004","volume":"75","author":"M Mahajan","year":"2009","unstructured":"Mahajan M, Raman V, Sikdar S. Parameterizing above or below guaranteed values. J. Comput. Syst. Sci., 2009, 75(2): 137\u2013153.","journal-title":"J. Comput. Syst. Sci."},{"issue":"8","key":"1474_CR42","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1016\/j.jcss.2009.04.002","volume":"75","author":"I Razgon","year":"2009","unstructured":"Razgon I, O'Sullivan B. Almost 2-SAT is fixed-parameter tractable. Journal of Computer and System Sciences, 2009, 75(8): 435\u2013450.","journal-title":"Journal of Computer and System Sciences"},{"issue":"7","key":"1474_CR43","first-page":"1","volume":"57","author":"J Wang","year":"2014","unstructured":"Wang J, Li W, Li S, Chen J. On the parameterized vertex cover problem for graphs with perfect matching. Science China Information Sciences, 2014, 57(7): 1\u201312.","journal-title":"Science China Information Sciences"},{"issue":"1","key":"1474_CR44","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0012-365X(79)90066-9","volume":"27","author":"R Deming","year":"1979","unstructured":"Deming R. Independence numbers of graphs\u2014An extension of the K\u00f6onig-Egerv\u00e1ry theorem. Discrete Mathematics, 1979, 27(1): 23\u201333.","journal-title":"Discrete Mathematics"},{"key":"1474_CR45","doi-asserted-by":"crossref","unstructured":"Chen J, Liu Y, Lu S, O'Sullivan B, Razgon I. A fixed-parameter algorithm for the directed feedback vertex set problem. Journal of the ACM, 2008, 55(5): Article No. 21.","DOI":"10.1145\/1411509.1411511"}],"container-title":["Journal of Computer Science and Technology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11390-014-1474-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11390-014-1474-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11390-014-1474-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,4]],"date-time":"2025-05-04T18:58:38Z","timestamp":1746385118000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11390-014-1474-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,9]]},"references-count":45,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2014,9]]}},"alternative-id":["1474"],"URL":"https:\/\/doi.org\/10.1007\/s11390-014-1474-1","relation":{},"ISSN":["1000-9000","1860-4749"],"issn-type":[{"type":"print","value":"1000-9000"},{"type":"electronic","value":"1860-4749"}],"subject":[],"published":{"date-parts":[[2014,9]]}}}