{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:49:14Z","timestamp":1770994154472,"version":"3.50.1"},"reference-count":24,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":4028,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[1995,10]]},"abstract":"Abstract<\/jats:title>Let (G<\/jats:italic>, <) be a finite graph G<\/jats:italic> with a linearly ordered vertex set V<\/jats:italic>. We consider the decision problem (G<\/jats:italic>, <)ORD to have as an instance an (unordered) graph \u0393 and as a question whether there exists a linear order \u2264 on V<\/jats:italic>(\u0393) and an order preserving graph isomorphism of (G<\/jats:italic>, <) onto an induced subgraph of \u0393. Several familiar classes of graph are characterized as the yes\u2010instances of (G<\/jats:italic>, < )ORD for appropriate choices of (G<\/jats:italic>, <). Here the complexity of (G<\/jats:italic>, <)ORD is investigated. We conjecture that for any 2\u2010connected graph G, G \u2260 Kk<\/jats:sub><\/jats:italic>, (G<\/jats:italic>, <)ORD is NP\u2010complete. This is verified for almost all 2\u2010connected graphs. Several related problems are formulated and discussed. \u00a9 1995 John Wiley & Sons, Inc.<\/jats:p>","DOI":"10.1002\/rsa.3240070304","type":"journal-article","created":{"date-parts":[[2007,6,2]],"date-time":"2007-06-02T01:24:09Z","timestamp":1180747449000},"page":"223-268","source":"Crossref","is-referenced-by-count":8,"title":["On the computational complexity of ordered subgraph recognition"],"prefix":"10.1002","volume":"7","author":[{"given":"Dwight","family":"Duffus","sequence":"first","affiliation":[]},{"given":"Mark","family":"Ginn","sequence":"additional","affiliation":[]},{"given":"Vojt\u011bch","family":"R\u00f6dl","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"The Probabilistic Method","author":"Alon N.","year":"1992"},{"key":"e_1_2_1_3_2","volume-title":"Graphs and Hypergraphs","author":"Berge C.","year":"1973"},{"key":"e_1_2_1_4_2","volume-title":"Topics on Perfect Graphs","author":"Berge C.","year":"1984"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1993.1012"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190110405"},{"key":"e_1_2_1_7_2","doi-asserted-by":"crossref","unstructured":"S. A.Cook The complexity of theorem\u2010providing procedures Proc. 3rd Annual ACM Symposium on Theory of Computing 1971 pp.151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-46908-4_25"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02992776"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01895716"},{"key":"e_1_2_1_11_2","first-page":"464","article-title":"A combinatorial problem in geometry","volume":"2","author":"Erd\u00f5s P.","year":"1935","journal-title":"Composito Math."},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1965.15.835"},{"key":"e_1_2_1_13_2","volume-title":"Computers and Intractability: A Guide to the Theory of NP\u2010Completeness","author":"Garey M.","year":"1978"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90059-1"},{"key":"e_1_2_1_15_2","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"Golumbic M.","year":"1980"},{"key":"e_1_2_1_16_2","first-page":"232","article-title":"Some results in finite graph ramsey theory","volume":"79","author":"Gunderson D.","year":"1990","journal-title":"Cong. Numer."},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.21236\/AD0705364"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_2_1_19_2","article-title":"The NP\u2010completeness column: an ongoing guide","author":"Johnson D. S.","journal-title":"J. Alg."},{"key":"e_1_2_1_20_2","volume-title":"Algorithmic Graph Theory","author":"McHugh J. A.","year":"1990"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90251-C"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-36.1.445"},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1137\/0208008"},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1971-016-5"},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1992-064-7"}],"container-title":["Random Structures & Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.3240070304","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.3240070304","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,16]],"date-time":"2023-10-16T00:42:52Z","timestamp":1697416972000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.3240070304"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,10]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1995,10]]}},"alternative-id":["10.1002\/rsa.3240070304"],"URL":"https:\/\/doi.org\/10.1002\/rsa.3240070304","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"value":"1042-9832","type":"print"},{"value":"1098-2418","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,10]]}}}