{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T14:09:38Z","timestamp":1742393378390},"reference-count":17,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":5703,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1991,3]]},"abstract":"Abstract<\/jats:title>Let S<\/jats:italic> be a family of arcs on a circle. A graph G<\/jats:italic> = (V,E)<\/jats:italic> is called a circular\u2010arc overlap graph for S<\/jats:italic> if (i) there is a one\u2010to\u2010one correspondence between V<\/jats:italic> and S<\/jats:italic> and (ii) two vertices in V<\/jats:italic> are adjacent if and only if the corresponding arcs in S<\/jats:italic> intersect but neither one of them contains the other. In this article, we present two polynomial time algorithms on circular\u2010arc overlap graphs. Given a circular\u2010arc overlap graph in the form of a family of n<\/jats:italic> arcs, the first algorithm obtains a maximum independent set in O<\/jats:italic>(n<\/jats:italic>2<\/jats:sup>) time and the second one finds a maximum clique in O<\/jats:italic>(n<\/jats:italic>5<\/jats:sup>) time.<\/jats:p>","DOI":"10.1002\/net.3230210205","type":"journal-article","created":{"date-parts":[[2007,5,12]],"date-time":"2007-05-12T10:22:50Z","timestamp":1178965370000},"page":"195-203","source":"Crossref","is-referenced-by-count":6,"title":["Polynomial time algorithms on circular\u2010arc overlap graphs"],"prefix":"10.1002","volume":"21","author":[{"given":"Toshinobu","family":"Kashiwabara","sequence":"first","affiliation":[]},{"given":"Sumio","family":"Masuda","sequence":"additional","affiliation":[]},{"given":"Kazuo","family":"Nakajima","sequence":"additional","affiliation":[]},{"given":"Toshio","family":"Fujisawa","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","unstructured":"A.ApostolicoandS.Hambrusch New clique and independent set algorithms for circle graphs. Technical Report CSD\u2010TR\u2010608 Dept. of Computer Sciences Purdue University West Lafayette IN (1986)."},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/5383.5387"},{"key":"e_1_2_1_4_2","volume-title":"Circle graphs. Technical Report NSO\u201021","author":"Buckingham M. A.","year":"1980"},{"key":"e_1_2_1_5_2","volume-title":"Graph Algorithms","author":"Even S.","year":"1979"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/0201013"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230030305"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230040407"},{"key":"e_1_2_1_9_2","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"Golumbic M. C.","year":"1980"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(85)90039-1"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(88)90023-5"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120410"},{"key":"e_1_2_1_13_2","unstructured":"W.\u2010L.HsuandK.Tsai Linear time algorithms on circular\u2010arc graphs.Proceedings of the 26th Annual Allerton Conference on Communication Control and Computing Monticello IL September (1988)842\u2013851."},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(85)90012-4"},{"key":"e_1_2_1_15_2","first-page":"91","article-title":"Maximum clique problem of rectangle graphs","volume":"1","author":"Lee D. T.","year":"1983","journal-title":"Adv. Comput. Res."},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/0217003"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230200203"},{"key":"e_1_2_1_18_2","unstructured":"C. S.RimandK.Nakajima Complexity results for rectangle intersection and overlap graphs. Technical Report UMIACS\u2010TR\u201088\u201063 Institute of Advanced Computer Studies University of Maryland College Park MD (1988)."}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230210205","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230210205","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,23]],"date-time":"2023-10-23T07:09:18Z","timestamp":1698044958000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230210205"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,3]]},"references-count":17,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1991,3]]}},"alternative-id":["10.1002\/net.3230210205"],"URL":"https:\/\/doi.org\/10.1002\/net.3230210205","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,3]]}}}