{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T13:56:47Z","timestamp":1778594207655,"version":"3.51.4"},"reference-count":14,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2014,4,23]],"date-time":"2014-04-23T00:00:00Z","timestamp":1398211200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2015,3]]},"abstract":"<jats:p>In this paper we prove that two local conditions involving the degrees and co-degrees in a graph can be used to determine whether a given vertex partition is Frieze\u2013Kannan regular. With a more refined version of these two local conditions we provide a deterministic algorithm that obtains a Frieze\u2013Kannan regular partition of any graph<jats:italic>G<\/jats:italic>in time<jats:italic>O<\/jats:italic>(|<jats:italic>V<\/jats:italic>(<jats:italic>G<\/jats:italic>)|<jats:sup>2<\/jats:sup>).<\/jats:p>","DOI":"10.1017\/s0963548314000200","type":"journal-article","created":{"date-parts":[[2014,4,23]],"date-time":"2014-04-23T09:26:50Z","timestamp":1398245210000},"page":"407-437","source":"Crossref","is-referenced-by-count":9,"title":["An Optimal Algorithm for Finding Frieze\u2013Kannan Regular Partitions"],"prefix":"10.1017","volume":"24","author":[{"suffix":"Jr","given":"DOMINGOS","family":"DELLAMONICA","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"SUBRAHMANYAM","family":"KALYANASUNDARAM","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"DANIEL M.","family":"MARTIN","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"VOJT\u011aCH","family":"R\u00d6DL","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ASAF","family":"SHAPIRA","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,4,23]]},"reference":[{"key":"S0963548314000200_ref11","first-page":"287","volume-title":"Regularity Lemmas for Graphs","author":"Schacht","year":"2010"},{"key":"S0963548314000200_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/PL00001621"},{"key":"S0963548314000200_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80013-2"},{"key":"S0963548314000200_ref10","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702408223"},{"key":"S0963548314000200_ref4","doi-asserted-by":"publisher","DOI":"10.1137\/110846373"},{"key":"S0963548314000200_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050052"},{"key":"S0963548314000200_ref6","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-11.4.261"},{"key":"S0963548314000200_ref13","first-page":"399","volume-title":"Probl\u00e8mes Combinatoires et Th\u00e9orie des Graphes","author":"Szemer\u00e9di","year":"1978"},{"key":"S0963548314000200_ref5","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793247634"},{"key":"S0963548314000200_ref12","doi-asserted-by":"crossref","first-page":"199","DOI":"10.4064\/aa-27-1-199-245","article-title":"On sets of integers containing no k elements in arithmetic progression","volume":"27","author":"Szemer\u00e9di","year":"1975","journal-title":"Acta Arith."},{"key":"S0963548314000200_ref14","doi-asserted-by":"crossref","unstructured":"Williams R. (2009) Private communication.","DOI":"10.4324\/9780203874998"},{"key":"S0963548314000200_ref8","first-page":"12","volume-title":"37th Annual Symposium on Foundations of Computer Science","author":"Frieze","year":"1996"},{"key":"S0963548314000200_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-012-0171-x"},{"key":"S0963548314000200_ref1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1005"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548314000200","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,9]],"date-time":"2019-08-09T16:44:26Z","timestamp":1565369066000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548314000200\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,4,23]]},"references-count":14,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,3]]}},"alternative-id":["S0963548314000200"],"URL":"https:\/\/doi.org\/10.1017\/s0963548314000200","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,4,23]]}}}