{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T08:11:54Z","timestamp":1725869514305},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319487489"},{"type":"electronic","value":"9783319487496"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-48749-6_35","type":"book-chapter","created":{"date-parts":[[2016,10,30]],"date-time":"2016-10-30T08:16:59Z","timestamp":1477815419000},"page":"477-488","source":"Crossref","is-referenced-by-count":3,"title":["On the Parameterized Parallel Complexity and the Vertex Cover Problem"],"prefix":"10.1007","author":[{"given":"Faisal N.","family":"Abu-Khzam","sequence":"first","affiliation":[]},{"given":"Shouwei","family":"Li","sequence":"additional","affiliation":[]},{"given":"Christine","family":"Markarian","sequence":"additional","affiliation":[]},{"given":"Friedhelm","family":"Meyer auf der Heide","sequence":"additional","affiliation":[]},{"given":"Pavel","family":"Podlipyan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,10,31]]},"reference":[{"key":"35_CR1","unstructured":"Abu-Khzam, F.N., Collins, R.L., Fellows, M.R., Langston, M.A., Suters, W.H., Symons, C.T.: Kernelization algorithms for the vertex cover problem,: theory and experiments. In: Arge, L., Italiano, G.F., Sedgewick, R. (eds.) Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithmics and Combinatorics, New Orleans, LA, USA, 10 January 2004, pp. 62\u201369. SIAM (2004)"},{"issue":"3","key":"35_CR2","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1007\/s00224-007-1328-0","volume":"41","author":"FN Abu-Khzam","year":"2007","unstructured":"Abu-Khzam, F.N., Fellows, M.R., Langston, M.A., Suters, W.H.: Crown structures for vertex cover kernelization. Theory Comput. Syst. 41(3), 411\u2013430 (2007)","journal-title":"Theory Comput. Syst."},{"key":"35_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1007\/978-3-319-42634-1_8","volume-title":"Computing and Combinatorics","author":"FN Abu-Khzam","year":"2016","unstructured":"Abu-Khzam, F.N., Li, S., Markarian, C., Meyer auf der Heide, F., Podlipyan, P.: The monotone circuit value problem with bounded genus is in NC. In: Dinh, T.N., Thai, M.T. (eds.) COCOON 2016. LNCS, vol. 9797, pp. 92\u2013102. Springer, Heidelberg (2016). doi: 10.1007\/978-3-319-42634-1_8"},{"key":"35_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1007\/978-3-540-70918-3_42","volume-title":"STACS 2007","author":"M Agrawal","year":"2007","unstructured":"Agrawal, M., Hoang, T.M., Thierauf, T.: The polynomially bounded perfect matching problem is in NC $$^2$$ . In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol. 4393, pp. 489\u2013499. Springer, Heidelberg (2007)"},{"key":"35_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"892","DOI":"10.1007\/BFb0057945","volume-title":"Euro-Par\u201998 Parallel Processing","author":"M Cesati","year":"1998","unstructured":"Cesati, M., Di Ianni, M.: Parameterized parallel complexity. In: Pritchard, D., Reeve, J.S. (eds.) Euro-Par 1998. LNCS, vol. 1470, pp. 892\u2013896. Springer, Heidelberg (1998)"},{"issue":"40","key":"35_CR6","doi-asserted-by":"crossref","first-page":"3736","DOI":"10.1016\/j.tcs.2010.06.026","volume":"411","author":"J Chen","year":"2010","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theor. Comput. Sci. 411(40), 3736\u20133756 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"35_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/978-3-540-30559-0_22","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"B Chor","year":"2004","unstructured":"Chor, B., Fellows, M., Juedes, D.W.: Linear kernels in linear time, or how to save k colors in O( $$n^2$$ ) steps. In: Hromkovi\u010d, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol. 3353, pp. 257\u2013269. Springer, Heidelberg (2004)"},{"key":"35_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1007\/3-540-51542-9_13","volume-title":"WADS 1989","author":"M Chrobak","year":"1989","unstructured":"Chrobak, M., Naor, J., Novick, M.B.: Using bounded degree spanning trees in the design of efficient algorithms on claw-free graphs. In: Dehne, F., Sack, J.-R., Santoro, N. (eds.) WADS 1989. LNCS, vol. 382, pp. 147\u2013162. Springer, Heidelberg (1989)"},{"issue":"3","key":"35_CR9","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1006\/jagm.1993.1046","volume":"15","author":"E Dahlhaus","year":"1993","unstructured":"Dahlhaus, E., Hajnal, P., Karpinski, M.: On the parallel complexity of hamiltonian cycle and matching problem on dense graphs. J. Algorithms 15(3), 367\u2013384 (1993)","journal-title":"J. Algorithms"},{"key":"35_CR10","unstructured":"Dahlhaus, E., Karpinski, M.: The matching problem for strongly chordal graphs is in NC. Inst. f\u00fcr Informatik, Univ. (1986)"},{"key":"35_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity, vol. 4. Springer, Heidelberg (2013)"},{"key":"35_CR12","doi-asserted-by":"crossref","unstructured":"Elberfeld, M., Kawarabayashi, K.-I.: Embedding and canonizing graphs of bounded genus in logspace. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pp. 383\u2013392. ACM (2014)","DOI":"10.1145\/2591796.2591865"},{"issue":"1\u20134","key":"35_CR13","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1080\/00207168408803413","volume":"15","author":"RK Ghosh","year":"1984","unstructured":"Ghosh, R.K., Bhattacharjee, G.: Parallel breadth-first search algorithms for trees and graphs. Int. J. Comput. Math. 15(1\u20134), 255\u2013268 (1984)","journal-title":"Int. J. Comput. Math."},{"issue":"2","key":"35_CR14","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1145\/1008354.1008356","volume":"9","author":"LM Goldschlager","year":"1977","unstructured":"Goldschlager, L.M.: The monotone and planar circuit value problems are log space complete for P. SIGACT News 9(2), 25\u201329 (1977)","journal-title":"SIGACT News"},{"key":"35_CR15","doi-asserted-by":"crossref","unstructured":"Grigoriev, D.Y., Karpinski, M.: The matching problem for bipartite graphs with polynomially bounded permanents is in NC. In: 28th Annual Symposium on Foundations of Computer Science, 1987, pp. 166\u2013172. IEEE (1987)","DOI":"10.1109\/SFCS.1987.56"},{"issue":"2","key":"35_CR16","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0020-0190(86)90141-9","volume":"22","author":"A Israeli","year":"1986","unstructured":"Israeli, A., Shiloach, Y.: An improved parallel algorithm for maximal matching. Inf. Process. Lett. 22(2), 57\u201360 (1986)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"35_CR17","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1145\/990518.990519","volume":"7","author":"RE Ladner","year":"1975","unstructured":"Ladner, R.E.: The circuit value problem is log space complete for P. SIGACT News 7(1), 18\u201320 (1975)","journal-title":"SIGACT News"},{"issue":"2","key":"35_CR18","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1109\/TC.1981.6312171","volume":"100","author":"GF Lev","year":"1981","unstructured":"Lev, G.F., Pippenger, N., Valiant, L.G.: A fast parallel algorithm for routing in permutation networks. IEEE Trans. Comput. 100(2), 93\u2013100 (1981)","journal-title":"IEEE Trans. Comput."},{"issue":"5","key":"35_CR19","doi-asserted-by":"crossref","first-page":"519","DOI":"10.1109\/12.926164","volume":"50","author":"K Li","year":"2001","unstructured":"Li, K., Pan, V.Y.: Parallel matrix multiplication on a linear array with a reconfigurable pipelined bus system. IEEE Trans. Comput. 50(5), 519\u2013525 (2001)","journal-title":"IEEE Trans. Comput."},{"key":"35_CR20","doi-asserted-by":"crossref","unstructured":"Mahajan, M., Varadarajan, K.R.: A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs. In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pp. 351\u2013357. ACM (2000)","DOI":"10.1145\/335305.335346"},{"issue":"1","key":"35_CR21","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/BF02088292","volume":"22","author":"S Miyano","year":"1989","unstructured":"Miyano, S.: The lexicographically first maximal subgraph problems: P-completeness and NC algorithms. Math. Syst. Theory 22(1), 47\u201373 (1989)","journal-title":"Math. Syst. Theory"},{"key":"35_CR22","volume-title":"The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)","author":"EL Post","year":"2016","unstructured":"Post, E.L.: The Two-Valued Iterative Systems of Mathematical Logic. (AM-5), vol. 5. Princeton University Press, Princeton (2016)"},{"key":"35_CR23","doi-asserted-by":"crossref","unstructured":"Yang, H.: An NC algorithm for the general planar monotone circuit value problem. In: Proceedings of the Third IEEE Symposium on Parallel and Distributed Processing, 1991, pp. 196\u2013203, December 1991","DOI":"10.1109\/SPDP.1991.218279"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-48749-6_35","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,25]],"date-time":"2017-06-25T02:24:37Z","timestamp":1498357477000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-48749-6_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319487489","9783319487496"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-48749-6_35","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}