{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T23:49:46Z","timestamp":1648856986083},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2010,11,9]],"date-time":"2010-11-09T00:00:00Z","timestamp":1289260800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2012,2]]},"DOI":"10.1007\/s00453-010-9470-5","type":"journal-article","created":{"date-parts":[[2010,11,8]],"date-time":"2010-11-08T12:45:59Z","timestamp":1289220359000},"page":"537-563","source":"Crossref","is-referenced-by-count":3,"title":["Finding Induced Paths of Given Parity in\u00a0Claw-Free Graphs"],"prefix":"10.1007","volume":"62","author":[{"given":"Pim","family":"van \u2019t\u00a0Hof","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcin","family":"Kami\u0144ski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dani\u00ebl","family":"Paulusma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,11,9]]},"reference":[{"issue":"2","key":"9470_CR1","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1145\/103516.103517","volume":"38","author":"E.M. Arkin","year":"1991","unstructured":"Arkin, E.M., Papadimitriou, C.H., Yannakakis,\u00a0M.: Modularity of cycles and paths in graphs. J. ACM 38(2), 255\u2013274 (1991)","journal-title":"J. ACM"},{"issue":"1\u20133","key":"9470_CR2","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0166-218X(93)90230-L","volume":"44","author":"S.R. Arikati","year":"1993","unstructured":"Arikati, S.R., Peled, U.N.: A\u00a0linear algorithm for the group path problem on chordal graphs. Discrete Appl. Math. 44(1\u20133), 185\u2013190 (1993)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"9470_CR3","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/0166-218X(95)00086-7","volume":"65","author":"S.R. Arikati","year":"1996","unstructured":"Arikati, S.R., Peled, U.N.: A\u00a0polynomial algorithm for the parity path problem on perfectly orientable graphs. Discrete Appl. Math. 65(1), 5\u201320 (1996)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"9470_CR4","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1007\/BF01931279","volume":"31","author":"S.R. Arikati","year":"1991","unstructured":"Arikati, S.R., Rangan, C.P., Manacher, G.K.: Efficient reduction for path problems on circular-arc graphs. BIT Numer. Math. 31(2), 182\u2013193 (1991)","journal-title":"BIT Numer. Math."},{"key":"9470_CR5","first-page":"114","volume":"10","author":"C. Berge","year":"1961","unstructured":"Berge,\u00a0C.: F\u00e4rbung von\u00a0Graphen, deren s\u00e4mtliche bzw. deren ungerade Kreise starr sind. Wiss. Z., Martin-Luther-Univ. Halle-Wittenb., Math.-Nat.wiss. Reihe 10, 114 (1961)","journal-title":"Wiss. Z., Martin-Luther-Univ. Halle-Wittenb., Math.-Nat.wiss. Reihe"},{"issue":"1","key":"9470_CR6","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0012-365X(91)90098-M","volume":"90","author":"D. Bienstock","year":"1991","unstructured":"Bienstock,\u00a0D.: On the complexity of testing for odd holes and induced odd paths. Discrete Math. 90(1), 85\u201392 (1991)","journal-title":"Discrete Math."},{"issue":"2","key":"9470_CR7","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/s00493-005-0012-8","volume":"25","author":"M. Chudnovsky","year":"2005","unstructured":"Chudnovsky,\u00a0M., Cornu\u00e9jols,\u00a0G., Liu,\u00a0X., Seymour, P.D., Vu\u0161kovi\u0107,\u00a0K.: Recognizing Berge graphs. Combinatorica 25(2), 143\u2013186 (2005)","journal-title":"Combinatorica"},{"issue":"2","key":"9470_CR8","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1002\/jgt.20040","volume":"48","author":"M. Chudnovsky","year":"2005","unstructured":"Chudnovsky,\u00a0M., Kawarabayashi,\u00a0K., Seymour, P.D.: Detecting even holes. J. Graph Theory 48(2), 85\u2013111 (2005)","journal-title":"J. Graph Theory"},{"key":"9470_CR9","doi-asserted-by":"crossref","first-page":"51","DOI":"10.4007\/annals.2006.164.51","volume":"164","author":"M. Chudnovsky","year":"2006","unstructured":"Chudnovsky,\u00a0M., Robertson,\u00a0N., Seymour, P.D., Thomas,\u00a0R.: The strong perfect graph theorem. Ann. Math. 164, 51\u2013229 (2006)","journal-title":"Ann. Math."},{"key":"9470_CR10","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/s00493-010-2334-4","volume":"30","author":"M. Chudnovsky","year":"2010","unstructured":"Chudnovsky,\u00a0M., Seymour, P.D.: The three-in-a-tree problem. Combinatorica 30, 387\u2013417 (2010)","journal-title":"Combinatorica"},{"key":"9470_CR11","unstructured":"Chudnovsky,\u00a0M., Seymour, P.D.: Three-colourable perfect graphs without even pairs. Submitted. Manuscript at www.columbia.edu\/~mc2775\/K4evenpairs.ps"},{"key":"9470_CR12","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1016\/0095-8956(88)90085-8","volume":"44","author":"V. Chv\u00e1tal","year":"1988","unstructured":"Chv\u00e1tal,\u00a0V., Sbihi,\u00a0N.: Recognizing claw-free perfect graphs. J. Comb. Theory, Ser. B 44, 154\u2013176 (1988)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9470_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/jctb.1993.1049","volume":"59","author":"D.G. Corneil","year":"1993","unstructured":"Corneil, D.G., Fonlupt,\u00a0J.: Stable set bonding in perfect graphs and parity graphs. J. Comb. Theory, Ser. B 59, 1\u201314 (1993)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9470_CR14","doi-asserted-by":"crossref","first-page":"3552","DOI":"10.1016\/j.dam.2009.02.009","volume":"157","author":"N. Derhy","year":"2009","unstructured":"Derhy,\u00a0N., Picouleau,\u00a0C.: Finding induced trees. Discrete Appl. Math. 157, 3552\u20133557 (2009)","journal-title":"Discrete Appl. Math."},{"key":"9470_CR15","volume-title":"Graph Theory","author":"R. Diestel","year":"2005","unstructured":"Diestel,\u00a0R.: Graph Theory, 3rd edn. Springer, Heidelberg (2005)","edition":"3"},{"key":"9470_CR16","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/S0012-365X(96)00174-4","volume":"165\u2013166","author":"H. Everett","year":"1997","unstructured":"Everett,\u00a0H., de Figueiredo, C.M.H., Sales, C.L., Maffray,\u00a0F., Porto,\u00a0O., Reed, B.A.: Path parity and perfection. Discrete Math. 165\u2013166, 233\u2013252 (1997)","journal-title":"Discrete Math."},{"key":"9470_CR17","first-page":"67","volume-title":"Perfect Graphs","author":"H. Everett","year":"2001","unstructured":"Everett,\u00a0H., de Figueiredo, C.M.H., Linhares Sales,\u00a0C., Maffray,\u00a0F., Porto,\u00a0O., Reed, B.A.: Even pairs. In: Ramirez-Alfonsin,\u00a0L., Reed, B.A. (eds.) Perfect Graphs, pp. 67\u201392. Wiley, New York (2001)"},{"issue":"1\u20133","key":"9470_CR18","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/S0166-218X(98)00139-5","volume":"91","author":"C.M.H. Figueiredo de","year":"1999","unstructured":"de Figueiredo, C.M.H., Gimbel, J.G., Mello, C.P., Szwarcfiter, J.L.: Even and odd pairs in comparability and in P 4-comparability graphs. Discrete Appl. Math. 91(1\u20133), 293\u2013297 (1999)","journal-title":"Discrete Appl. Math."},{"key":"9470_CR19","first-page":"83","volume":"16","author":"J. Fonlupt","year":"1982","unstructured":"Fonlupt,\u00a0J., Uhry, J.P.: Transformations which preserve perfectness and H-perfectness of graphs. Ann. Discrete Math. 16, 83\u201385 (1982)","journal-title":"Ann. Discrete Math."},{"key":"9470_CR20","doi-asserted-by":"crossref","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"D.R. Fulkerson","year":"1965","unstructured":"Fulkerson, D.R., Gross, O.A.: Incidence matrices and interval graphs. Pac. J. Math. 15, 835\u2013855 (1965)","journal-title":"Pac. J. Math."},{"key":"9470_CR21","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/0012-365X(77)90030-9","volume":"19","author":"F. Gavril","year":"1977","unstructured":"Gavril,\u00a0F.: Algorithms on clique separable graphs. Discrete Math. 19, 159\u2013165 (1977)","journal-title":"Discrete Math."},{"issue":"1","key":"9470_CR22","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1137\/S0895480197329089","volume":"13","author":"C.T. Ho\u00e0ng","year":"2000","unstructured":"Ho\u00e0ng, C.T., Le, V.B.: Recognizing perfect 2-split graphs. SIAM J. Discrete Math. 13(1), 48\u201355 (2000)","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"9470_CR23","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1145\/23005.31330","volume":"34","author":"W.-L. Hsu","year":"1987","unstructured":"Hsu, W.-L.: Recognizing planar perfect graphs. J. ACM 34(2), 255\u2013288 (1987)","journal-title":"J. ACM"},{"key":"9470_CR24","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1002\/net.3230140403","volume":"14","author":"A.S. LaPaugh","year":"1984","unstructured":"LaPaugh, A.S., Papadimitriou, C.H.: The even-path problem for graphs and digraphs. Networks 14, 507\u2013513 (1984)","journal-title":"Networks"},{"key":"9470_CR25","doi-asserted-by":"crossref","first-page":"3540","DOI":"10.1016\/j.dam.2009.02.015","volume":"157","author":"B. L\u00e9v\u00eaque","year":"2009","unstructured":"L\u00e9v\u00eaque,\u00a0B., Lin, D.Y., Maffray,\u00a0F., Trotignon,\u00a0N.: Detecting induced subgraphs. Discrete Appl. Math. 157, 3540\u20133551 (2009)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"9470_CR26","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1007\/s10878-005-1775-y","volume":"9","author":"X. Li","year":"2005","unstructured":"Li,\u00a0X., Zang,\u00a0W.: A\u00a0combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs. J. Comb. Optim. 9(4), 331\u2013347 (2005)","journal-title":"J. Comb. Optim."},{"key":"9470_CR27","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1006\/jctb.1998.1841","volume":"74","author":"C. Linhares Sales","year":"1998","unstructured":"Linhares Sales,\u00a0C., Maffray,\u00a0F.: Even pairs in claw-free perfect graphs. J. Comb. Theory, Ser. B 74, 169\u2013191 (1998)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9470_CR28","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1006\/jctb.1998.1872","volume":"75","author":"F. Maffray","year":"1999","unstructured":"Maffray,\u00a0F., Reed, B.A.: A\u00a0description of claw-free perfect graphs. J. Comb. Theory, Ser. B 75, 134\u2013156 (1999)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9470_CR29","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1016\/S0195-6698(87)80037-9","volume":"8","author":"H. Meyniel","year":"1987","unstructured":"Meyniel,\u00a0H.: A\u00a0new property of critical imperfect graphs and some consequences. Eur. J. Comb. 8, 313\u2013316 (1987)","journal-title":"Eur. J. Comb."},{"issue":"2","key":"9470_CR30","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1137\/1003021","volume":"3","author":"S. Parter","year":"1961","unstructured":"Parter,\u00a0S.: The use of linear graphs in Gauss elimination. SIAM Rev. 3(2), 119\u2013130 (1961)","journal-title":"SIAM Rev."},{"key":"9470_CR31","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1016\/0020-0190(73)90029-X","volume":"2","author":"N.D. Roussopoulos","year":"1973","unstructured":"Roussopoulos, N.D.: A\u00a0max\u2009{m,n} algorithm for determining the graph H from its line graph G. Inf. Process. Lett. 2, 108\u2013112 (1973)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"9470_CR32","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"D.J. Rose","year":"1976","unstructured":"Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5(2), 266\u2013283 (1976)","journal-title":"SIAM J. Comput."},{"key":"9470_CR33","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1016\/S1571-0653(04)00256-2","volume":"7","author":"R.M. Sampaio","year":"2001","unstructured":"Sampaio, R.M., Sales, C.L.: On the complexity of finding even pairs in planar perfect graphs. Electron. Notes Discrete Math. 7, 186\u2013189 (2001)","journal-title":"Electron. Notes Discrete Math."},{"issue":"3","key":"9470_CR34","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/0166-218X(95)00065-Y","volume":"68","author":"C.R. Satyan","year":"1996","unstructured":"Satyan, C.R., Rangan, C.P.: The parity path problem on some subclasses of perfect graphs. Discrete Appl. Math. 68(3), 293\u2013302 (1996)","journal-title":"Discrete Appl. Math."},{"key":"9470_CR35","series-title":"Lecture Notes in Computer Science","first-page":"329","volume-title":"Proceedings of the 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2009)","author":"S. Shrem","year":"2009","unstructured":"Shrem,\u00a0S., Stern,\u00a0M., Golumbic, M.C.: Smallest odd holes in claw-free graphs. In: Proceedings of the 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2009). Lecture Notes in Computer Science, vol.\u00a05911, pp.\u00a0329\u2013340. (2009)"},{"key":"9470_CR36","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/0012-365X(85)90051-2","volume":"55","author":"R.E. Tarjan","year":"1985","unstructured":"Tarjan, R.E.: Decomposition by clique separators. Discrete Math. 55, 221\u2013232 (1985)","journal-title":"Discrete Math."},{"key":"9470_CR37","unstructured":"Trotignon,\u00a0N.: Graphes parfaits: structure et algorithmes. PhD Thesis, Universit\u00e9 Joseph Fourier, Grenoble I (2004) (in French)"},{"key":"9470_CR38","first-page":"281","volume":"21","author":"S.H. Whitesides","year":"1984","unstructured":"Whitesides, S.H.: A\u00a0method for solving certain graph recognition and optimization problems, with applications to perfect graphs. Ann. Discrete Math. 21, 281\u2013297 (1984)","journal-title":"Ann. Discrete Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9470-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9470-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9470-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:06Z","timestamp":1559123106000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9470-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,11,9]]},"references-count":38,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2012,2]]}},"alternative-id":["9470"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9470-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,11,9]]}}}