A simple linear time algorithm for the isomorphism problem on proper circular-arc graphs

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 (pr...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L.
Formato: SER
Materias:
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
Linear times
Pca models
Polynomial times
Programming languages
Recognition algorithms
Cavity resonators
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_03029743_v5124LNCS_n_p355_Lin
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_03029743_v5124LNCS_n_p355_Lin
record_format dspace
spelling todo:paper_03029743_v5124LNCS_n_p355_Lin2023-10-03T15:19:05Z A simple linear time algorithm for the isomorphism problem on proper circular-arc graphs Lin, M.C. Soulignac, F.J. Szwarcfiter, J.L. 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 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. Fil:Lin, M.C. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Soulignac, F.J. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. SER info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_03029743_v5124LNCS_n_p355_Lin
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic 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
spellingShingle 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
Lin, M.C.
Soulignac, F.J.
Szwarcfiter, J.L.
A simple linear time algorithm for the isomorphism problem on proper circular-arc graphs
topic_facet 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
description 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.
format SER
author Lin, M.C.
Soulignac, F.J.
Szwarcfiter, J.L.
author_facet Lin, M.C.
Soulignac, F.J.
Szwarcfiter, J.L.
author_sort Lin, M.C.
title A simple linear time algorithm for the isomorphism problem on proper circular-arc graphs
title_short A simple linear time algorithm for the isomorphism problem on proper circular-arc graphs
title_full A simple linear time algorithm for the isomorphism problem on proper circular-arc graphs
title_fullStr A simple linear time algorithm for the isomorphism problem on proper circular-arc graphs
title_full_unstemmed A simple linear time algorithm for the isomorphism problem on proper circular-arc graphs
title_sort simple linear time algorithm for the isomorphism problem on proper circular-arc graphs
url http://hdl.handle.net/20.500.12110/paper_03029743_v5124LNCS_n_p355_Lin
work_keys_str_mv AT linmc asimplelineartimealgorithmfortheisomorphismproblemonpropercirculararcgraphs
AT soulignacfj asimplelineartimealgorithmfortheisomorphismproblemonpropercirculararcgraphs
AT szwarcfiterjl asimplelineartimealgorithmfortheisomorphismproblemonpropercirculararcgraphs
AT linmc simplelineartimealgorithmfortheisomorphismproblemonpropercirculararcgraphs
AT soulignacfj simplelineartimealgorithmfortheisomorphismproblemonpropercirculararcgraphs
AT szwarcfiterjl simplelineartimealgorithmfortheisomorphismproblemonpropercirculararcgraphs
_version_ 1782029336348459008

Ejemplares similares