caa a22 4500 445805056 CHVBK 20180317145154.0 cr unu---uuuuu 170323e20110201xx s 000 0 eng 10.1007/s00453-009-9304-5 doi (NATIONALLICENCE)springer-10.1007/s00453-009-9304-5 Linear-Time Recognition of Helly Circular-Arc Models and Graphs [Elektronische Daten] [Benson Joeris, Min Lin, Ross McConnell, Jeremy Spinrad, Jayme Szwarcfiter] A circular-arc model ℳ is a circle C together with a collection $\mathcal{A}$ of arcs of C. If $\mathcal{A}$ satisfies the Helly Property then ℳ is a Helly circular-arc model. A (Helly) circular-arc graph is the intersection graph of a (Helly) circular-arc model. Circular-arc graphs and their subclasses have been the object of a great deal of attention in the literature. Linear-time recognition algorithms have been described both for the general class and for some of its subclasses. However, for Helly circular-arc graphs, the best recognition algorithm is that by Gavril, whose complexity is O(n 3). In this article, we describe different characterizations for Helly circular-arc graphs, including a characterization by forbidden induced subgraphs for the class. The characterizations lead to a linear-time recognition algorithm for recognizing graphs of this class. The algorithm also produces certificates for a negative answer, by exhibiting a forbidden subgraph of it, within this same bound. Springer Science+Business Media, LLC, 2009 Algorithms nationallicence Circular-arc graphs nationallicence Forbidden subgraphs nationallicence Helly circular-arc graphs nationallicence Joeris Benson Computer Science Department, Colorado State University, 80523-1873, Fort Collins, CO, USA aut Lin Min Facultad de Ciencias Exactas y Naturales, Departamento de Computación, Universidad de Buenos Aires, Buenos Aires, Argentina aut McConnell Ross Computer Science Department, Colorado State University, 80523-1873, Fort Collins, CO, USA aut Spinrad Jeremy Computer Science Department, Vanderbilt University, 37235, Nashville, TN, USA aut Szwarcfiter Jayme Instituto de Matemática, NCE and COPPE, Universidade Federal do Rio de Janeiro, Caixa Postal 2324, 20001-970, Rio de Janeiro, RJ, Brazil aut Algorithmica Springer-Verlag 59/2(2011-02-01), 215-239 0178-4617 59:2<215 2011 59 453 https://doi.org/10.1007/s00453-009-9304-5 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9304-5 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Joeris Benson Computer Science Department, Colorado State University, 80523-1873, Fort Collins, CO, USA aut NATIONALLICENCE 700 1- Lin Min Facultad de Ciencias Exactas y Naturales, Departamento de Computación, Universidad de Buenos Aires, Buenos Aires, Argentina aut NATIONALLICENCE 700 1- McConnell Ross Computer Science Department, Colorado State University, 80523-1873, Fort Collins, CO, USA aut NATIONALLICENCE 700 1- Spinrad Jeremy Computer Science Department, Vanderbilt University, 37235, Nashville, TN, USA aut NATIONALLICENCE 700 1- Szwarcfiter Jayme Instituto de Matemática, NCE and COPPE, Universidade Federal do Rio de Janeiro, Caixa Postal 2324, 20001-970, Rio de Janeiro, RJ, Brazil aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 59/2(2011-02-01), 215-239 0178-4617 59:2<215 2011 59 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer