{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,16]],"date-time":"2024-09-16T19:12:42Z","timestamp":1726513962436},"reference-count":12,"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":6068,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1990,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Let <jats:italic>F<\/jats:italic> = {<jats:italic>I<\/jats:italic><jats:sub>1<\/jats:sub>, <jats:italic>I<\/jats:italic><jats:sub>2<\/jats:sub>,\u2026,<jats:italic>I<\/jats:italic><jats:sub>n<\/jats:sub>} be a finite family of closed intervals on the real line. Two intervals <jats:italic>I<\/jats:italic><jats:sub>j<\/jats:sub> and <jats:italic>I<\/jats:italic><jats:sub>k<\/jats:sub> in <jats:italic>F<\/jats:italic> are said to overlap each other if they intersect but neither one of them contains the other. A graph <jats:italic>G<\/jats:italic> = (<jats:italic>V<\/jats:italic>, <jats:italic>E<\/jats:italic>) is called an overlap graph for <jats:italic>F<\/jats:italic> if there is a one\u2010to\u2010one correspondence between <jats:italic>V<\/jats:italic> and <jats:italic>F<\/jats:italic> such that two vertices in <jats:italic>V<\/jats:italic> are adjacent to each other if and only if the corresponding intervals in <jats:italic>F<\/jats:italic> overlap each other. In this paper, we present two efficient algorithms for finding maximum cliques of an overlap graph when it is given in the form of a family of <jats:italic>n<\/jats:italic> intervals. The first algorithm finds a maximum clique in <jats:italic>O<\/jats:italic> (<jats:italic>n<\/jats:italic>. log <jats:italic>n<\/jats:italic> + <jats:italic>Min<\/jats:italic> {<jats:italic>m, n<\/jats:italic>\u2010 \u03c9}) time, where <jats:italic>m<\/jats:italic> is the number of edges and \u03c9 is the size of a maximum clique, respectively, of the graph. The second algorithm generates all maximum cliques in <jats:italic>O<\/jats:italic> (<jats:italic>n<\/jats:italic> \u2010 log <jats:italic>n<\/jats:italic> + <jats:italic>m<\/jats:italic> + \u03b3) time, where \u03b3 is the total sum of their sizes.<\/jats:p>","DOI":"10.1002\/net.3230200203","type":"journal-article","created":{"date-parts":[[2007,5,12]],"date-time":"2007-05-12T08:49:47Z","timestamp":1178959787000},"page":"157-171","source":"Crossref","is-referenced-by-count":16,"title":["Efficient algorithms for finding maximum cliques of an overlap graph"],"prefix":"10.1002","volume":"20","author":[{"given":"Sumio","family":"Masuda","sequence":"first","affiliation":[]},{"given":"Kazuo","family":"Nakajima","sequence":"additional","affiliation":[]},{"given":"Toshinobu","family":"Kashiwabara","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","volume-title":"The Design and Analysis of Computer Algorithms","author":"Aho A. V.","year":"1974"},{"key":"e_1_2_1_3_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_4_2","unstructured":"M. A.Buckingham Circle graphs. Technical Report NSO\u201021 Courant Institute of Mathematical Sciences New York University New York (1980)."},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90103-X"},{"key":"e_1_2_1_6_2","volume-title":"Computers and Intractability\u2010A Guide to the Theory of NP\u2010Completeness","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/0201013"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230030305"},{"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.1137\/0214018"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(84)90037-3"},{"key":"e_1_2_1_12_2","unstructured":"S.Masuda K.Nakajima T.Kashiwabara andT.Fujisawa Efficient algorithms for finding maximum cliques of an overlap graph. Technical Report SRC\u2010TR\u201086\u201058. Systems Research Center University of Maryland College Park MD (1986)."},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230110305"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230200203","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230200203","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,22]],"date-time":"2023-10-22T07:25:08Z","timestamp":1697959508000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230200203"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,3]]},"references-count":12,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1990,3]]}},"alternative-id":["10.1002\/net.3230200203"],"URL":"https:\/\/doi.org\/10.1002\/net.3230200203","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1990,3]]}}}