Navegar

Colección

Datos Estadísticas

Artículo

Lin, M.C.; Soulignac, F.J.; Szwarcfiter, J.L. "A simple linear time algorithm for the isomorphism problem on proper circular-arc graphs" (2008) 11th Scandinavian Workshop on Algorithm Theory, SWAT 2008. 5124 LNCS:355-366
La versión final de este artículo es de uso interno. El editor solo permite incluir en el repositorio el artículo en su versión post-print. Por favor, si usted la posee enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

A circular-arc model is a circle C together with a collection of arcs of C. If no arc is contained in any other then is a proper circular-arc model, and if some point of C is not covered by any arc then is an interval model. A (proper) (interval) circular-arc graph is the intersection graph of a (proper) (interval) 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. For the isomorphism problem, there exists a polynomial time algorithm for the general case, and a linear time algorithm for interval graphs. In this work we develop a linear time algorithm for the isomorphism problem in proper circular-arc graphs, based on uniquely encoding a proper circular-arc model. Our method relies on results about uniqueness of certain PCA models, developed by Deng, Hell and Huang in [6]. The algorithm is easy to code and uses only basic tools available in almost every programming language. © 2008 Springer-Verlag Berlin Heidelberg.

Registro:

Documento: Artículo
Título:A simple linear time algorithm for the isomorphism problem on proper circular-arc graphs
Autor:Lin, M.C.; Soulignac, F.J.; Szwarcfiter, J.L.
Ciudad:Gothenburg
Filiación:Facultad de Ciencias Exactas y Naturales, Departamento de Computación, Universidad de Buenos Aires, Buenos Aires, Argentina
Instituto de Matemática, NCE and COPPE, Universidade Federal do Rio de Janeiro, Caixa Postal 2324, 20001-970 Rio de Janeiro, RJ, Brazil
Palabras clave:Isomorphism problems; Proper circular-arc canonization; Proper circular-arc graphs; Algorithms; BASIC (programming language); Boolean functions; Computer programming languages; Graph theory; Polynomial approximation; Problem oriented languages; Set theory; Technical presentations; Arc models; Encoding; General classes; Intersection graphs; Interval graphs; Interval models; Isomorphism problems; Linear times; Pca models; Polynomial times; Programming languages; Proper circular-arc canonization; Proper circular-arc graphs; Recognition algorithms; Cavity resonators
Año:2008
Volumen:5124 LNCS
Página de inicio:355
Página de fin:366
DOI: http://dx.doi.org/10.1007/978-3-540-69903-3_32
Título revista:11th Scandinavian Workshop on Algorithm Theory, SWAT 2008
Título revista abreviado:Lect. Notes Comput. Sci.
ISSN:03029743
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v5124LNCS_n_p355_Lin

Referencias:

  • Bhattacharya, B., Hell, P., Huang, J., A linear algorithm for maximum weight cliques in proper circular arc graphs (1996) SIAM J. Discrete Math, 9 (2), pp. 274-289
  • Booth, K.S., Lexicographically least circular substrings (1980) Inform. Process. Lett, 10 (4-5), pp. 240-242
  • Booth, K.S., Lueker, G.S., Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms (1976) J. Comput. System Sci, 13 (3), pp. 335-379
  • Brandstädt, A., Le, V.B., Spinrad, J.P., (1999) Graph classes: A survey, , SIAM, Philadelphia
  • Corneil, D.G., Olariu, S., Stewart, L., The ultimate interval graph recognition algorithm (extended abstract) (1998) 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 175-180. , ACM, New York
  • Deng, X., Hell, P., Huang, J., Linear-time representation algorithms for proper circular-arc graphs and proper interval graphs (1996) SIAM J. Comput, 25 (2), pp. 390-403
  • Garey, M.R., Johnson, D.S., (1979) Computers and intractability, , W. H. Freeman and Co, San Francisco
  • Golumbic, M.C., (2004) Algorithmic Graph Theory and Perfect Graphs, , 2nd edn. North-Holland Publishing Go, Amsterdam
  • Habib, M., McConnell, R.M., Paul, C., Viennot, L., Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing (2000) Theoret. Comput. Sci, 234 (1-2), pp. 59-84
  • Hsu, W.: A simple test for interval graphs. In: Mayr, E.W. (ed.) WG 1992. LNCS, 657, pp. 11-16. Springer, Heidelberg (1993); Hsu, W., O(m, n) algorithms for the recognition and isomorphism problems on circular-arc graphs (1995) SIAM J. Comput, 24 (3), pp. 411-439
  • Kaplan, H., Nussbaum, Y.: A simpler linear-time recognition of circular-arc graphs. In: Arge, L., Freivalds, R. (eds.) SWAT 2006. LNCS, 4059, pp. 41-52. Springer, Heidelberg (2006); Kaplan, H., Nussbaum, Y.: Certifying algorithms for recognizing proper circulararc graphs and unit circular-arc graphs. In: Fomin. F.V. (ed.) WG 2006. LNCS, 4271, pp. 289-300. Springer, Heidelberg (2006); Korte, N., Möhring, R.H., An incremental linear-time algorithm for recognizing interval graphs (1989) SIAM J. Comput, 18 (1), pp. 68-81
  • Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L.: Proper Helly circular-arc graphs. In: Brandstädt, A., Kratsch, D., Müller, H. (eds.) WG 2007. LNCS, pp. 248-257. Springer, Heidelberg (2007); Lin, M.C., Szwarcfiter, J.L., Unit Circular-Arc Graph Representations and Feasible Circulations (2008) SIAM J. Discrete Math, 22 (1), pp. 409-423
  • Lueker, G.S., Booth, K.S.: A linear time algorithm for deciding interval graph isomorphism. J. Assoc. Comput. Mach. 26(2), 183-195 (1979); McConnell, R.M., Linear-time recognition of circular-arc graphs (2003) Algorithmica, 37 (2), pp. 93-147
  • Roberts, F.S., Indifference graphs (1969) Proof Techniques in Graph Theory (2nd Ann Arbor Graph Theory Conf.), pp. 139-146. , Academic Press, New York
  • Shiloach, Y., Fast canonization of circular strings (1981) J. Algorithms, 2 (2), pp. 107-121
  • Spinrad, J.P., (2003) Efficient graph representations, , American Mathematical Society, ProvidenceA4 - Lindholmen Science Park; Chalmers; Ericsson; Lecture Notes in Computer Science; City of Goteborg

Citas:

---------- APA ----------
Lin, M.C., Soulignac, F.J. & Szwarcfiter, J.L. (2008) . A simple linear time algorithm for the isomorphism problem on proper circular-arc graphs. 11th Scandinavian Workshop on Algorithm Theory, SWAT 2008, 5124 LNCS, 355-366.
http://dx.doi.org/10.1007/978-3-540-69903-3_32
---------- CHICAGO ----------
Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L. "A simple linear time algorithm for the isomorphism problem on proper circular-arc graphs" . 11th Scandinavian Workshop on Algorithm Theory, SWAT 2008 5124 LNCS (2008) : 355-366.
http://dx.doi.org/10.1007/978-3-540-69903-3_32
---------- MLA ----------
Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L. "A simple linear time algorithm for the isomorphism problem on proper circular-arc graphs" . 11th Scandinavian Workshop on Algorithm Theory, SWAT 2008, vol. 5124 LNCS, 2008, pp. 355-366.
http://dx.doi.org/10.1007/978-3-540-69903-3_32
---------- VANCOUVER ----------
Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L. A simple linear time algorithm for the isomorphism problem on proper circular-arc graphs. Lect. Notes Comput. Sci. 2008;5124 LNCS:355-366.
http://dx.doi.org/10.1007/978-3-540-69903-3_32