{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T11:16:25Z","timestamp":1725880585454},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319539249"},{"type":"electronic","value":"9783319539256"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"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":[[2017]]},"DOI":"10.1007\/978-3-319-53925-6_14","type":"book-chapter","created":{"date-parts":[[2017,2,19]],"date-time":"2017-02-19T20:12:36Z","timestamp":1487535156000},"page":"177-189","source":"Crossref","is-referenced-by-count":0,"title":["Recognizing Simple-Triangle Graphs by Restricted 2-Chain Subgraph Cover"],"prefix":"10.1007","author":[{"given":"Asahi","family":"Takaoka","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,2,21]]},"reference":[{"issue":"3","key":"14_CR1","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","volume":"8","author":"B Aspvall","year":"1979","unstructured":"Aspvall, B., Plass, M.F., Tarjan, R.E.: A linear-time algorithm for testing the truth of certain quantified boolean formulas. Inf. Process. Lett. 8(3), 121\u2013123 (1979)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"14_CR2","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/s11083-010-9144-6","volume":"27","author":"KP Bogart","year":"2010","unstructured":"Bogart, K.P., Laison, J.D., Ryan, S.P.: Triangle, parallelogram, and trapezoid orders. Order 27(2), 163\u2013175 (2010)","journal-title":"Order"},{"key":"14_CR3","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/j.endm.2008.01.021","volume":"30","author":"MR Cerioli","year":"2008","unstructured":"Cerioli, M.R., de Oliveira, F.S., Szwarcfiter, J.L.: Linear-interval dimension and PI orders. Electron. Notes Discrete Math. 30, 111\u2013116 (2008)","journal-title":"Electron. Notes Discrete Math."},{"issue":"1","key":"14_CR4","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1002\/net.3230110103","volume":"11","author":"CJ Colbourn","year":"1981","unstructured":"Colbourn, C.J.: On testing isomorphism of permutation graphs. Networks 11(1), 13\u201321 (1981)","journal-title":"Networks"},{"key":"14_CR5","first-page":"267","volume":"58","author":"DG Corneil","year":"1987","unstructured":"Corneil, D.G., Kamula, P.A.: Extensions of permutation and interval graphs. Congr. Numer. 58, 267\u2013275 (1987)","journal-title":"Congr. Numer."},{"issue":"1","key":"14_CR6","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0166-218X(88)90032-7","volume":"21","author":"I Dagan","year":"1988","unstructured":"Dagan, I., Golumbic, M.C., Pinter, R.Y.: Trapezoid graphs and their coloring. Discrete Appl. Math. 21(1), 35\u201346 (1988)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"14_CR7","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/s10479-010-0792-0","volume":"188","author":"S Dantas","year":"2011","unstructured":"Dantas, S., de Figueiredo, C.M.H., Golumbic, M.C., Klein, S., Maffray, F.: The chain graph sandwich problem. Ann. Oper. Res. 188(1), 133\u2013139 (2011)","journal-title":"Ann. Oper. Res."},{"issue":"3","key":"14_CR8","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1006\/jagm.1995.1047","volume":"19","author":"MC Golumbic","year":"1995","unstructured":"Golumbic, M.C., Kaplan, H., Shamir, R.: Graph sandwich problems. J. Algorithms 19(3), 449\u2013473 (1995)","journal-title":"J. Algorithms"},{"issue":"1","key":"14_CR9","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0012-365X(83)90019-5","volume":"43","author":"MC Golumbic","year":"1983","unstructured":"Golumbic, M.C., Rotem, D., Urrutia, J.: Comparability graphs and intersection graphs. Discrete Math. 43(1), 37\u201346 (1983)","journal-title":"Discrete Math."},{"issue":"1","key":"14_CR10","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/BF01202237","volume":"13","author":"P Hell","year":"1997","unstructured":"Hell, P., Huang, J.: Two remarks on circular arc graphs. Graphs Comb. 13(1), 65\u201372 (1997)","journal-title":"Graphs Comb."},{"key":"14_CR11","first-page":"241","volume":"11","author":"T Ibaraki","year":"1981","unstructured":"Ibaraki, T., Peled, U.: Sufficient conditions for graphs to have threshold number 2. Ann. Discrete Math. 11, 241\u2013268 (1981)","journal-title":"Ann. Discrete Math."},{"key":"14_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1007\/978-3-642-33090-2_58","volume-title":"Algorithms \u2013 ESA 2012","author":"P Klav\u00edk","year":"2012","unstructured":"Klav\u00edk, P., Kratochv\u00edl, J., Krawczyk, T., Walczak, B.: Extending partial representations of function graphs and permutation graphs. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol. 7501, pp. 671\u2013682. Springer, Heidelberg (2012). doi: 10.1007\/978-3-642-33090-2_58"},{"issue":"2","key":"14_CR13","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1145\/322123.322125","volume":"26","author":"GS Lueker","year":"1979","unstructured":"Lueker, G.S., Booth, K.S.: A linear time algorithm for deciding interval graph isomorphism. J. ACM 26(2), 183\u2013195 (1979)","journal-title":"J. ACM"},{"issue":"2","key":"14_CR14","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1006\/jagm.1994.1034","volume":"17","author":"TH Ma","year":"1994","unstructured":"Ma, T.H., Spinrad, J.P.: On the 2-chain subgraph cover and related problems. J. Algorithms 17(2), 251\u2013268 (1994)","journal-title":"J. Algorithms"},{"key":"14_CR15","series-title":"Ann. Discrete Math.","volume-title":"Threshold Graphs and Related Topics","author":"N Mahadev","year":"1995","unstructured":"Mahadev, N., Peled, U.: Threshold Graphs and Related Topics. Ann. Discrete Math., vol. 56. Elsevier Science B.V., Amsterdam (1995)"},{"issue":"1\u20133","key":"14_CR16","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/S0012-365X(98)00319-7","volume":"201","author":"RM McConnell","year":"1999","unstructured":"McConnell, R.M., Spinrad, J.P.: Modular decomposition and transitive orientation. Discrete Math. 201(1\u20133), 189\u2013241 (1999)","journal-title":"Discrete Math."},{"key":"14_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1007\/978-3-642-40450-4_61","volume-title":"Algorithms \u2013 ESA 2013","author":"GB Mertzios","year":"2013","unstructured":"Mertzios, G.B.: The recognition of simple-triangle graphs and of linear-interval orders is polynomial. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol. 8125, pp. 719\u2013730. Springer, Heidelberg (2013). doi: 10.1007\/978-3-642-40450-4_61"},{"issue":"3","key":"14_CR18","doi-asserted-by":"crossref","first-page":"1150","DOI":"10.1137\/140963108","volume":"29","author":"GB Mertzios","year":"2015","unstructured":"Mertzios, G.B.: The recognition of simple-triangle graphs and of linear-interval orders is polynomial. SIAM J. Discrete Math. 29(3), 1150\u20131185 (2015)","journal-title":"SIAM J. Discrete Math."},{"key":"14_CR19","doi-asserted-by":"crossref","unstructured":"Raschle, T., Simon, K.: Recognition of graphs with threshold dimension two. In: STOC 1995, pp. 650\u2013661. ACM, New York (1995)","DOI":"10.1145\/225058.225283"},{"issue":"15","key":"14_CR20","doi-asserted-by":"crossref","first-page":"1650","DOI":"10.1016\/j.dam.2010.06.002","volume":"158","author":"AMS Shrestha","year":"2010","unstructured":"Shrestha, A.M.S., Tayu, S., Ueno, S.: On orthogonal ray graphs. Discrete Appl. Math. 158(15), 1650\u20131659 (2010)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"14_CR21","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1016\/0095-8956(88)90038-X","volume":"44","author":"JP Spinrad","year":"1988","unstructured":"Spinrad, J.P.: Circular-arc graphs with clique cover number two. J. Comb. Theory Ser. B 44(3), 300\u2013306 (1988)","journal-title":"J. Comb. Theory Ser. B"},{"key":"14_CR22","doi-asserted-by":"crossref","DOI":"10.1090\/fim\/019","volume-title":"Efficient Graph Representations, Fields Institute Monographs","author":"JP Spinrad","year":"2003","unstructured":"Spinrad, J.P.: Efficient Graph Representations, Fields Institute Monographs, vol. 19. American Mathematical Society, Providence (2003)"},{"issue":"8","key":"14_CR23","doi-asserted-by":"crossref","first-page":"1838","DOI":"10.1587\/transfun.E98.A.1838","volume":"98\u2013A","author":"A Takaoka","year":"2015","unstructured":"Takaoka, A.: Graph isomorphism completeness for trapezoid graphs. IEICE Trans. Fundam. 98\u2013A(8), 1838\u20131840 (2015)","journal-title":"IEICE Trans. Fundam."},{"issue":"11","key":"14_CR24","doi-asserted-by":"crossref","first-page":"2327","DOI":"10.1587\/transinf.E96.D.2327","volume":"96\u2013D","author":"A Takaoka","year":"2014","unstructured":"Takaoka, A., Tayu, S., Ueno, S.: Dominating sets and induced matchings in orthogonal ray graphs. IEICE Trans. Inf. Syst. 96\u2013D(11), 2327\u20132332 (2014)","journal-title":"IEICE Trans. Inf. Syst."},{"issue":"2","key":"14_CR25","first-page":"87","volume":"16","author":"R Uehara","year":"2014","unstructured":"Uehara, R.: The graph isomorphism problem on geometric graphs. Discrete Math. Theoret. Comput. Sci. 16(2), 87\u201396 (2014)","journal-title":"Discrete Math. Theoret. Comput. Sci."},{"issue":"3","key":"14_CR26","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1137\/0603036","volume":"3","author":"M Yannakakis","year":"1982","unstructured":"Yannakakis, M.: The complexity of the partial order dimension problem. SIAM J. Algebraic Discrete Methods 3(3), 351\u2013358 (1982)","journal-title":"SIAM J. Algebraic Discrete Methods"}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-53925-6_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,18]],"date-time":"2019-09-18T17:30:36Z","timestamp":1568827836000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-53925-6_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319539249","9783319539256"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-53925-6_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}