Artículo
Durán, G.; Fernández Slezak, F.; Grippo, L.N.; Oliveira, F.; Szwarcfiter, J.L. "Recognition and characterization of unit interval graphs with integer endpoints" (2017) Discrete Applied Mathematics. 245:168-176
Consulte la política de Acceso Abierto del editor
Abstract:
We study those unit interval graphs having a model with intervals of integer endpoints and prescribed length. We present a structural result for this graph subclass which leads to a quadratic-time recognition algorithm, giving as positive certificate a model of minimum total length and as negative certificate a forbidden induced subgraph. We also present a quadratic-time algorithm to build, given a unit interval graph, a unit interval model with integer endpoints for which the interval length is as minimum as possible. © 2017 Elsevier B.V.
Registro:
| Documento: | Artículo |
| Título: | Recognition and characterization of unit interval graphs with integer endpoints |
| Autor: | Durán, G.; Fernández Slezak, F.; Grippo, L.N.; Oliveira, F.; Szwarcfiter, J.L. |
| Filiación: | CONICET, Argentina Instituto de Cálculo, FCEN, Universidad de Buenos Aires, Argentina Depto. de Matemática, FCEN, Universidad de Buenos Aires, Argentina Depto. de Ingeniería Industrial, FCFM, Universidad de Chile, Chile Instituto de Ciencias, UNGS, Los Polvorines, Buenos Aires, Argentina Instituto de Matemática e Estatística, UERJ, Rio de Janeiro, Brazil IM, COPPE and NCE, UFRJ, Rio de Janeiro, Brazil |
| Palabras clave: | Forbidden induced subgraphs; Proper interval graphs; Unit interval graphs; Combinatorial mathematics; Mathematical techniques; Forbidden induced subgraphs; Induced subgraphs; Proper interval graphs; Quadratic time; Quadratic time algorithms; Recognition algorithm; Unit interval graphs; Unit intervals; Graphic methods |
| Año: | 2017 |
| Volumen: | 245 |
| Página de inicio: | 168 |
| Página de fin: | 176 |
| DOI: | http://dx.doi.org/10.1016/j.dam.2017.04.013 |
| Título revista: | Discrete Applied Mathematics |
| Título revista abreviado: | Discrete Appl Math |
| ISSN: | 0166218X |
| CODEN: | DAMAD |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v245_n_p168_Duran |
Referencias:
- Corneil, D.G., Kim, H., Natarajan, S., Olariu, S., Sprague, A.P., Simple linear time recognition of unit interval graphs (1995) Inf. Process. Lett., 55 (2), pp. 99-104
- Costa, V., Dantas, S., Sankoff, D., Xu, X., Gene clusters as intersections of powers of paths (2012) J. Braz. Comput. Soc., 18 (2), pp. 129-136
- Durán, G., Fernández Slezak, F., Grippo, L., Oliveira, F., Szwarcfiter, J.L., On unit interval graphs with integer endpoints (2015) Electron. Notes Discrete Math., 50, pp. 445-450
- Habib, M., Paul, C., Viennot, L., A synthesis on partition refinement: A useful routine for strings, graphs, Boolean matrices and automata (1998), pp. 25-38. , 15th Annual STACS, Paris, France; Kratsch, D., McConnell, R.M., Mehlhorn, K., Spinrad, J.P., Certifying algorithms for recognizing interval graphs and permutation graphs (2006) SIAM J. Comput., 36 (2), pp. 326-353
- Lekkerkerker, C., Boland, D., Representation of finite graphs by a set of intervals on the real line (1962) Fund. Math., 51, pp. 45-64
- Mitas, J., (1994) Minimal Representation of Semiorders with Intervals of Same Length Orders, Algorithms and Applications, LNCS, 831, pp. 162-175. , Springer-Verlag
- Pirlot, M., Minimal representation of a semiorder (1990) Theory and Decision, 28, pp. 109-141
- Roberts, F.S., Indifference graphs (1969) Proof Techniques in Graph Theory, Proc. Second Ann Arbor Graph Theory Conf. Ann Arbor, pp. 139-146. , Mich. Academic Press New York
- Soulignac, F., http://arxiv.org/abs/12076960, Bounded Minimal, and Short Representations of Unit Interval and Unit Circular-arc Graphs., 2014; West, D.B., (2001) Introduction To Graph Theory, , second ed. Prentice Hall
Citas:
---------- APA ----------
Durán, G., Fernández Slezak, F., Grippo, L.N., Oliveira, F. & Szwarcfiter, J.L. (2017) . Recognition and characterization of unit interval graphs with integer endpoints. Discrete Applied Mathematics, 245, 168-176.http://dx.doi.org/10.1016/j.dam.2017.04.013
---------- CHICAGO ----------
Durán, G., Fernández Slezak, F., Grippo, L.N., Oliveira, F., Szwarcfiter, J.L. "Recognition and characterization of unit interval graphs with integer endpoints" . Discrete Applied Mathematics 245 (2017) : 168-176.http://dx.doi.org/10.1016/j.dam.2017.04.013
---------- MLA ----------
Durán, G., Fernández Slezak, F., Grippo, L.N., Oliveira, F., Szwarcfiter, J.L. "Recognition and characterization of unit interval graphs with integer endpoints" . Discrete Applied Mathematics, vol. 245, 2017, pp. 168-176.http://dx.doi.org/10.1016/j.dam.2017.04.013
---------- VANCOUVER ----------
Durán, G., Fernández Slezak, F., Grippo, L.N., Oliveira, F., Szwarcfiter, J.L. Recognition and characterization of unit interval graphs with integer endpoints. Discrete Appl Math. 2017;245:168-176.http://dx.doi.org/10.1016/j.dam.2017.04.013
