Artículo
Durán, G.; Fernández Slezak, F.; Grippo, L.N.; de S. Oliveira, F.; Szwarcfiter, J. "On unit interval graphs with integer endpoints" (2015) Electronic Notes in Discrete Mathematics. 50:445-450
Consulte la política de Acceso Abierto del editor
Abstract:
We study those unit interval graphs having a model with intervals of prescribed integer length. We present a structural result for this subclass which leads to a quadratic-time recognition algorithm of it, giving as positive certificate a model of minimum total length and as negative certificate a forbidden induced subgraph. © 2015 Elsevier B.V.
Registro:
| Documento: | Artículo |
| Título: | On unit interval graphs with integer endpoints |
| Autor: | Durán, G.; Fernández Slezak, F.; Grippo, L.N.; de S. Oliveira, F.; Szwarcfiter, J. |
| 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 subgraphs; Proper interval graphs; Unit interval graphs |
| Año: | 2015 |
| Volumen: | 50 |
| Página de inicio: | 445 |
| Página de fin: | 450 |
| DOI: | http://dx.doi.org/10.1016/j.endm.2015.07.074 |
| Título revista: | Electronic Notes in Discrete Mathematics |
| Título revista abreviado: | Electron. Notes Discrete Math. |
| ISSN: | 15710653 |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v50_n_p445_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
- Habib, M., Paul, C., Viennot, L., A Synthesis on Partition Refinement: A Useful Routine for Strings, Graphs, Boolean Matrices and Automata (1998) 15th Annual STACS, pp. 25-38. , Paris, France
- Knuth, D., Sorting and Searching (1998) The Art of Computer Programming, , Addison-Wesley Publishing Company, Boston, MA, USA
- Kratsch, D., McConnell, R.M., Mehlhorn, K., Spinrad, J.P., Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs (2006) SIA Journal on Computing, 36 (2), pp. 326-353
- Lekkerkerker, C., Boland, D., Representation of Finite Graphs by a Set of Intervals on the Real Line (1962) Fundamenta Mathematicae, 51, pp. 45-64
- Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L., Short Models for Unit Interval Graphs (2009) Electronic Notes in Discrete Mathematics, 35, pp. 247-255
- Mitas, J., Minimal Representation of Semiorders with Intervals of Same Length, Orders, algorithms and applications (1994) 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) Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., pp. 139-146. , Academic Press, New York, Proof Techniques in Graph Theory
- Soulignac, F., Bounded, Minimal, and Short Representations of Unit Interval and Unit Circular-arc Graphs, , http://arxiv.org/abs/1207.6960
- West, D.B., (2001) Introduction to Graph Theory, , Prentice Hall
Citas:
---------- APA ----------
Durán, G., Fernández Slezak, F., Grippo, L.N., de S. Oliveira, F. & Szwarcfiter, J. (2015) . On unit interval graphs with integer endpoints. Electronic Notes in Discrete Mathematics, 50, 445-450.http://dx.doi.org/10.1016/j.endm.2015.07.074
---------- CHICAGO ----------
Durán, G., Fernández Slezak, F., Grippo, L.N., de S. Oliveira, F., Szwarcfiter, J. "On unit interval graphs with integer endpoints" . Electronic Notes in Discrete Mathematics 50 (2015) : 445-450.http://dx.doi.org/10.1016/j.endm.2015.07.074
---------- MLA ----------
Durán, G., Fernández Slezak, F., Grippo, L.N., de S. Oliveira, F., Szwarcfiter, J. "On unit interval graphs with integer endpoints" . Electronic Notes in Discrete Mathematics, vol. 50, 2015, pp. 445-450.http://dx.doi.org/10.1016/j.endm.2015.07.074
---------- VANCOUVER ----------
Durán, G., Fernández Slezak, F., Grippo, L.N., de S. Oliveira, F., Szwarcfiter, J. On unit interval graphs with integer endpoints. Electron. Notes Discrete Math. 2015;50:445-450.http://dx.doi.org/10.1016/j.endm.2015.07.074
