{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:09:31Z","timestamp":1761620971997},"reference-count":33,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2007,10]]},"abstract":"<jats:p> The longest path problem is the one that finds a longest path in a given graph. While the graph classes in which the Hamiltonian path problem can be solved efficiently are widely investigated, few graph classes are known to be solved efficiently for the longest path problem. Among those, for trees, a simple linear time algorithm for the longest path problem is known. We first generalize the algorithm, and show that the longest path problem can be solved efficiently for some tree-like graph classes by this approach. We next propose two new graph classes that have natural interval representations, and show that the longest path problem can be solved efficiently on these classes. <\/jats:p>","DOI":"10.1142\/s0129054107005054","type":"journal-article","created":{"date-parts":[[2007,9,21]],"date-time":"2007-09-21T05:49:00Z","timestamp":1190353740000},"page":"911-930","source":"Crossref","is-referenced-by-count":31,"title":["ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES"],"prefix":"10.1142","volume":"18","author":[{"given":"RYUHEI","family":"UEHARA","sequence":"first","affiliation":[{"name":"Department of Information Processing, School of Information Science, Japan Advanced Institute of Science and Technology (JAIST), Ishikawa 923-1292, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"YUSHI","family":"UNO","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Information Sciences, Graduate School of Science, Osaka Prefecture University, Sakai 599-8531, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-58412-1"},{"key":"rf4","volume-title":"Hypergraphs","author":"Berge C.","year":"1989"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90078-9"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(86)90135-3"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702416761"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80045-1"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796"},{"key":"rf10","first-page":"273","volume":"67","author":"Brandst\u00e4dt A.","journal-title":"Ars Combinatoria"},{"key":"rf11","first-page":"165","volume":"58","author":"Brandst\u00e4dt A.","journal-title":"Congressus Numerantium"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(01)00198-3"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(80)90069-6"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90059-8"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(93)90223-G"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"rf18","volume-title":"Computers and Intractability \u2014 A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979"},{"key":"rf19","series-title":"Annals of Discrete Mathematics","volume-title":"Algorithmic Graph Theory and Perfect Graphs","volume":"57","author":"Golumbic M. C.","year":"2004"},{"key":"rf21","volume-title":"Approximation Algorithms for NP-hard Problems","author":"Hochbaum D.","year":"1995"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523689"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(85)90050-X"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00173-2"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1137\/0218005"},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(96)00014-5"},{"key":"rf27","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(93)E0077-H"},{"key":"rf28","first-page":"239","volume":"25","author":"Monien B.","journal-title":"Annals of Discrete Mathematics"},{"key":"rf29","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(95)00057-4"},{"key":"rf30","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(97)00027-9"},{"key":"rf31","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(03)00298-9"},{"key":"rf32","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(85)90000-7"},{"key":"rf33","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(02)00433-2"},{"key":"rf34","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(87)80003-3"},{"key":"rf36","volume-title":"Approximation Algorithms","author":"Vazirani V. V.","year":"2001"},{"key":"rf38","doi-asserted-by":"publisher","DOI":"10.1137\/0210022"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054107005054","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T20:41:33Z","timestamp":1565124093000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054107005054"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10]]},"references-count":33,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2007,10]]}},"alternative-id":["10.1142\/S0129054107005054"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1142\/s0129054107005054","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,10]]}}}