{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T21:17:30Z","timestamp":1770326250592,"version":"3.49.0"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2011,11,26]],"date-time":"2011-11-26T00:00:00Z","timestamp":1322265600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/2.0"},{"start":{"date-parts":[[2011,11,26]],"date-time":"2011-11-26T00:00:00Z","timestamp":1322265600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/2.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Braz Comput Soc"],"published-print":{"date-parts":[[2012,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The<jats:italic>interval count problem<\/jats:italic>determines the smallest number of interval lengths needed in order to represent an interval model of a given interval graph or interval order. Despite the large number of studies about interval graphs and interval orders, surprisingly only a few results on the interval count problem are known. In this work, we provide a short survey about the interval count and related problems. a graph and the number of its maximal cliques.<\/jats:p>","DOI":"10.1007\/s13173-011-0047-1","type":"journal-article","created":{"date-parts":[[2011,11,25]],"date-time":"2011-11-25T12:37:26Z","timestamp":1322224646000},"page":"103-112","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["The interval count of interval graphs and orders: a short survey"],"prefix":"10.1007","volume":"18","author":[{"given":"M\u00e1rcia R.","family":"Cerioli","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabiano","family":"de S.\u00a0Oliveira","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jayme L.","family":"Szwarcfiter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,11,26]]},"reference":[{"key":"47_CR1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-1-4832-1447-4.50033-X","volume-title":"Maintaining knowledge about temporal intervals","author":"JF Allen","year":"1990","unstructured":"Allen JF (1990) Maintaining knowledge about temporal intervals. Morgan Kaufmann, San Mateo"},{"key":"47_CR2","volume-title":"Reasoning about plans","author":"JF Allen","year":"1991","unstructured":"Allen JF, Kautz HA, Pelavin RN, Tenenberg JD (1991) Reasoning about plans. Morgan Kaufmann, San Mateo"},{"issue":"11","key":"47_CR3","doi-asserted-by":"publisher","first-page":"1607","DOI":"10.1073\/pnas.45.11.1607","volume":"45","author":"S Benzer","year":"1959","unstructured":"Benzer S (1959) On the topology of the genetic fine structure. Proc Natl Acad Sci USA 45(11):1607\u20131620","journal-title":"Proc Natl Acad Sci USA"},{"issue":"1\u20133","key":"47_CR4","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0012-365X(98)00310-0","volume":"201","author":"KP Bogart","year":"1999","unstructured":"Bogart KP, West DB (1999) A short proof that \u201cproper = unit\u201d. Discrete Math 201(1\u20133):21\u201323","journal-title":"Discrete Math"},{"key":"47_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84628-970-5","volume-title":"Graph theory","author":"JA Bondy","year":"2008","unstructured":"Bondy JA, Murty USR (2008) Graph theory. Springer, Berlin"},{"key":"47_CR6","unstructured":"Brandst\u00e4dt A, Le VB, Szymczak T, Siegemund F Information system on graph class inclusions. http:\/\/wwwteo.informatik.uni-rostock.de\/isgci\/"},{"key":"47_CR7","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/978-1-4684-5547-2_5","volume-title":"Biotechnology and the human genome","author":"AV Carrano","year":"1988","unstructured":"Carrano AV (1988) Establishing the order to human chromosome-specific DNA fragments. In: Woodhead A, Barnhart B (eds) Biotechnology and the human genome. Plenum Press, New York, pp 37\u201350"},{"key":"47_CR8","first-page":"21","volume":"79","author":"MR Cerioli","year":"2006","unstructured":"Cerioli MR, Szwarcfiter JL (2006) Characterizing intersection graphs of substars of a star. Ars Comb 79:21\u201331","journal-title":"Ars Comb"},{"issue":"7","key":"47_CR9","doi-asserted-by":"publisher","first-page":"532","DOI":"10.1016\/j.dam.2010.07.006","volume":"159","author":"MR Cerioli","year":"2011","unstructured":"Cerioli MR, Oliveira FS, Szwarcfiter JL (2011) On counting interval lengths of interval graphs. Discrete Appl Math 159(7):532\u2013543","journal-title":"Discrete Appl Math"},{"key":"47_CR10","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1037\/h0020070","volume":"80","author":"CH Coombs","year":"1973","unstructured":"Coombs CH, Smith JEK (1973) On the detection of structures in attitudes and developmental processes. Psychol Rev 80:337\u2013351","journal-title":"Psychol Rev"},{"issue":"3","key":"47_CR11","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1016\/j.dam.2003.07.001","volume":"138","author":"DG Corneil","year":"2004","unstructured":"Corneil DG (2004) A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs. Discrete Appl Math 138(3):371\u2013379","journal-title":"Discrete Appl Math"},{"issue":"2","key":"47_CR12","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0020-0190(95)00046-F","volume":"55","author":"DG Corneil","year":"1995","unstructured":"Corneil DG, Kim H, Natarajan S, Olariu S, Sprague AP (1995) Simple linear time recognition of unit interval graphs. Inf Process Lett 55(2):99\u2013104","journal-title":"Inf Process Lett"},{"issue":"3","key":"47_CR13","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/0020-0190(95)00133-W","volume":"56","author":"CMH de Figueiredo","year":"1995","unstructured":"de Figueiredo CMH, Meidanis J, de Mello CP (1995) A linear-time algorithm for proper interval graph recognition. Inf Process Lett 56(3):179\u2013184","journal-title":"Inf Process Lett"},{"issue":"2","key":"47_CR14","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1137\/S0097539792269095","volume":"25","author":"X Deng","year":"1996","unstructured":"Deng X, Hell P, Huang J (1996) Linear-time representation algorithms for proper circular-arc graphs and proper interval graphs. SIAM J Comput 25(2):390\u2013403","journal-title":"SIAM J Comput"},{"key":"47_CR15","volume-title":"Interval orders and interval graphs","author":"PC Fishburn","year":"1985","unstructured":"Fishburn PC (1985) Interval orders and interval graphs. Wiley, New York"},{"issue":"22","key":"47_CR16","doi-asserted-by":"publisher","first-page":"2906","DOI":"10.1016\/j.disc.2006.04.043","volume":"307","author":"F Gardi","year":"2007","unstructured":"Gardi F (2007) The Roberts characterization of proper and unit interval graphs. Discrete Math 307(22):2906\u20132908","journal-title":"Discrete Math"},{"key":"47_CR17","volume-title":"Algorithmic graph theory and perfect graphs","author":"MC Golumbic","year":"2004","unstructured":"Golumbic MC (2004) Algorithmic graph theory and perfect graphs, 2nd edn. Amsterdam, Elsevier","edition":"2"},{"key":"47_CR18","unstructured":"Greenough T (1974) The representation and enumeration of interval orders. PhD thesis, Darthmouth College"},{"issue":"3","key":"47_CR19","doi-asserted-by":"publisher","first-page":"554","DOI":"10.1137\/S0895480103430259","volume":"18","author":"P Hell","year":"2005","unstructured":"Hell P, Huang J (2005) Certifying lexbfs recognition algorithms for proper interval graphs and proper interval bigraphs. SIAM J Discrete Math 18(3):554\u2013570","journal-title":"SIAM J Discrete Math"},{"key":"47_CR20","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0166-218X(93)90229-H","volume":"33","author":"G Isaak","year":"1993","unstructured":"Isaak G (1993) Discrete interval graphs with bounded representation. Discrete Appl Math 33:157\u2013183","journal-title":"Discrete Appl Math"},{"key":"47_CR21","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1145\/167088.167170","volume-title":"STOC \u201993","author":"RM Karp","year":"1993","unstructured":"Karp RM (1993) Mapping the genome: some combinatorial problems arising in molecular biology. In: STOC \u201993. ACM, New York, pp 278\u2013285"},{"key":"47_CR22","doi-asserted-by":"publisher","first-page":"565","DOI":"10.2140\/pjm.1969.28.565","volume":"28","author":"DG Kendall","year":"1969","unstructured":"Kendall DG (1969) Incidence matrices, interval graphs, and seriation in archaeology. Pac J Math 28:565\u2013570","journal-title":"Pac J Math"},{"key":"47_CR23","unstructured":"Leibowitz R (1978) Interval counts and threshold graphs. PhD thesis, Rutgers University"},{"issue":"4","key":"47_CR24","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1137\/0603049","volume":"3","author":"R Leibowitz","year":"1982","unstructured":"Leibowitz R, Assmann SF, Peck GW (1982) The interval count of a graph. SIAM J Algebr Discrete Methods 3(4):485\u2013494","journal-title":"SIAM J Algebr Discrete Methods"},{"key":"47_CR25","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-54316-3","volume-title":"Temporally distributed symptoms in technical diagnosis","author":"K N\u00f6kel","year":"1991","unstructured":"N\u00f6kel K (1991) Temporally distributed symptoms in technical diagnosis. Springer, Berlin"},{"issue":"3","key":"47_CR26","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1137\/0208031","volume":"8","author":"CH Papadimitriou","year":"1979","unstructured":"Papadimitriou CH, Yannakakis M (1979) Scheduling interval-ordered tasks. SIAM J Comput 8(3):405\u2013409","journal-title":"SIAM J Comput"},{"issue":"4","key":"47_CR27","doi-asserted-by":"publisher","first-page":"662","DOI":"10.1137\/S0895480196306373","volume":"10","author":"I Pe\u2019er","year":"1997","unstructured":"Pe\u2019er I, Shamir R (1997) Realizing interval graphs with size and distance constraints. SIAM J Discrete Math 10(4):662\u2013687","journal-title":"SIAM J Discrete Math"},{"key":"47_CR28","first-page":"139","volume-title":"Proof techniques in graph theory","author":"FS Roberts","year":"1969","unstructured":"Roberts FS (1969) Indifference graphs. In: Harary F (ed) Proof techniques in graph theory. Academic Press, San Diego, pp 139\u2013146"},{"key":"47_CR29","volume-title":"Discrete mathematical models with applications to social, biological, and environmental problems","author":"FS Roberts","year":"1976","unstructured":"Roberts FS (1976) Discrete mathematical models with applications to social, biological, and environmental problems. Prentice Hall, New York"},{"key":"47_CR30","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/0166-218X(84)90080-5","volume":"8","author":"D Skrien","year":"1984","unstructured":"Skrien D (1984) Chronological orderings of interval graphs. Discrete Appl Math 8:69\u201383","journal-title":"Discrete Appl Math"},{"key":"47_CR31","first-page":"45","volume-title":"Applications of discrete mathematics","author":"WT Trotter","year":"1988","unstructured":"Trotter WT (1988) Interval graphs, interval orders, and their generalizations. In: Applications of discrete mathematics. SIAM, Philadelphia, pp 45\u201358"},{"key":"47_CR32","doi-asserted-by":"crossref","DOI":"10.56021\/9780801844256","volume-title":"Combinatorics and partially ordered sets","author":"WT Trotter","year":"1992","unstructured":"Trotter WT (1992) Combinatorics and partially ordered sets. The Johns Hopkins University Press, Baltimore"},{"key":"47_CR33","volume-title":"Computation structures","author":"SA Ward","year":"1990","unstructured":"Ward SA, Halstead RH (1990) Computation structures. MIT Press & McGraw-Hill, Cambridge"}],"container-title":["Journal of the Brazilian Computer Society"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13173-011-0047-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s13173-011-0047-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s13173-011-0047-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13173-011-0047-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,11]],"date-time":"2023-06-11T09:10:49Z","timestamp":1686474649000},"score":1,"resource":{"primary":{"URL":"https:\/\/journal-bcs.springeropen.com\/articles\/10.1007\/s13173-011-0047-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,11,26]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["47"],"URL":"https:\/\/doi.org\/10.1007\/s13173-011-0047-1","relation":{},"ISSN":["0104-6500","1678-4804"],"issn-type":[{"value":"0104-6500","type":"print"},{"value":"1678-4804","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,11,26]]},"assertion":[{"value":"4 October 2011","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 October 2011","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 November 2011","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}