Navegar

Colección

Datos Estadísticas

Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

We present a fully dynamic algorithm for the recognition of proper circular-arc (PCA) graphs. The allowed operations on the graph involve the insertion and removal of vertices (together with its incident edges) or edges. Edge operations cost O(logn) time, where n is the number of vertices of the graph, while vertex operations cost O(logn+d) time, where d is the degree of the modified vertex. We also show incremental and decremental algorithms that work in O(1) time per inserted or removed edge. As part of our algorithm, fully dynamic connectivity and co-connectivity algorithms that work in O(logn) time per operation are obtained. Also, an O(Δ) time algorithm for determining if a PCA representation corresponds to a co-bipartite graph is provided, where Δ is the maximum among the degrees of the vertices. When the graph is co-bipartite, a co-bipartition of each of its co-components is obtained within the same amount of time. As an application, we show how to find a minimal forbidden induced subgraph of a static graph in O(n+m) time. © 2013, Springer Science+Business Media New York.

Registro:

Documento: Artículo
Título:Fully Dynamic Recognition of Proper Circular-Arc Graphs
Autor:Soulignac, F.J.
Filiación:CONICET, Buenos Aires, Argentina
Departamento de Computación, FCEN, Universidad de Buenos Aires, Buenos Aires, Argentina
Palabras clave:Co-connectivity; Dynamic recognition; Minimal forbidden induced subgraphs; Proper circular-arc graphs; Round graphs; Algorithms; Graphic methods; Connectivity algorithms; Decremental algorithms; Dynamic recognition; Forbidden induced subgraphs; Fully dynamic algorithms; Induced subgraphs; Proper circular-arc graphs; Round graphs; Graph theory
Año:2015
Volumen:71
Número:4
Página de inicio:904
Página de fin:968
DOI: http://dx.doi.org/10.1007/s00453-013-9835-7
Título revista:Algorithmica
Título revista abreviado:Algorithmica
ISSN:01784617
CODEN:ALGOE
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01784617_v71_n4_p904_Soulignac

Referencias:

  • Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C., (2009) Introduction to Algorithms, , MIT Press, Cambridge:
  • Corneil, D.G., A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs (2004) Discrete Appl. Math., 138 (3), pp. 371-379
  • 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
  • Crespelle, C., Fully dynamic representations of interval graphs (2010) Graph-Theoretic Concepts in Computer Science, pp. 77-87. , Lecture Notes in Comput. Sci., 5911, Springer, Berlin:
  • Crespelle, C., Paul, C., Fully dynamic recognition algorithm and certificate for directed cographs (2006) Discrete Appl. Math., 154 (12), pp. 1722-1741
  • Crespelle, C., Paul, C., Fully dynamic algorithm for recognition and modular decomposition of permutation graphs (2010) Algorithmica, 58 (2), pp. 405-432
  • 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
  • Eppstein, D., Galil, Z., Italiano, G.F., Dynamic graph algorithms (1999) Algorithms and Theory of Computation Handbook, pp. 1-25. , CRC Press, Boca Raton:
  • Herrera de Figueiredo, C.M., Meidanis, J., Picinin de Mello, C., A linear-time algorithm for proper interval graph recognition (1995) Inf. Process. Lett., 56 (3), pp. 179-184
  • Heggernes, P., Mancini, F., Dynamically maintaining split graphs (2009) Discrete Appl. Math., 157 (9), pp. 2057-2069
  • Hell, P., Huang, J., Certifying LexBFS recognition algorithms for proper interval graphs and proper interval bigraphs (2004) SIAM J. Discrete Math., 18 (3), pp. 554-570
  • Hell, P., Shamir, R., Sharan, R., A fully dynamic algorithm for recognizing and representing proper interval graphs (2001) SIAM J. Comput., 31 (1), pp. 289-305
  • Huang, J.: Tournament-like oriented graphs. Ph.D. thesis http://ir.lib.sfu.ca/handle/1892/5293, Simon Fraser University (1992). Accessed 15 February 2013; Huang, J., On the structure of local tournaments (1995) J. Comb. Theory, Ser. B, 63 (2), pp. 200-221
  • Ibarra, L., Fully dynamic algorithms for chordal graphs and split graphs (2008) ACM Trans. Algorithms, 4 (4)
  • Ibarra, L., A fully dynamic graph algorithm for recognizing proper interval graphs (2009) WALCOM—Algorithms and Computation, pp. 190-201. , Lecture Notes in Comput. Sci., 5431, Springer, Berlin:
  • Ibarra, L., A fully dynamic graph algorithm for recognizing interval graphs (2010) Algorithmica, 58 (3), pp. 637-678
  • Kaplan, H., Nussbaum, Y., Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs (2009) Discrete Appl. Math., 157 (15), pp. 3216-3230
  • Lekkerkerker, C.G., Boland, J.C., Representation of a finite graph by a set of intervals on the real line (1962) Fundam. Math., 51, pp. 45-64
  • Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L., A simple linear time algorithm for the isomorphism problem on proper circular-arc graphs (2008) Algorithm Theory—SWAT 2008, pp. 355-366. , Lecture Notes in Comput. Sci., 5124, Springer, Berlin:
  • Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L., Normal Helly circular-arc graphs and its subclasses (2013) Discrete Appl. Math., 161 (7-8), pp. 1037-1059
  • Lin, M.C., Szwarcfiter, J.L., Characterizations and recognition of circular-arc graphs and subclasses: a survey (2009) Discrete Math., 309 (18), pp. 5618-5635
  • McConnell, R.M., Mehlhorn, K., Näher, S., Schweitzer, P., Certifying algorithms (2011) Comput. Sci. Rev., 5 (2), pp. 119-161
  • Nikolopoulos, S.D., Palios, L., Papadopoulos, C., A fully dynamic algorithm for the recognition of P 4-sparse graphs (2012) Theor. Comput. Sci., 439, pp. 41-57
  • Roberts, F.S., Indifference graphs (1969) Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968), pp. 139-146. , Academic Press, New York:
  • Shamir, R., Sharan, R., A fully dynamic algorithm for modular decomposition and recognition of cographs (2004) Discrete Appl. Math., 136 (2-3), pp. 329-340
  • On proper and Helly circular-arc graphs. Ph.D. thesis, Universidad de Buenos Aires (2010). Accessed 15 February 2013 Soulignac, F.J, , http://digital.bl.fcen.uba.ar/Download/Tesis/Tesis_4660_Soulignac.pdf
  • Tarjan, R.E., (1983) Data Structures and Network Algorithms, , CBMS-NSF Regional Conference Series in Applied Mathematics, 44, SIAM, Philadelphia:
  • Tedder, M., Corneil, D., An optimal, edges-only fully dynamic algorithm for distance-hereditary graphs (2007) STACS 2007, pp. 344-355. , Lecture Notes in Comput. Sci., 4393, Springer, Berlin:
  • Tucker, A., Structure theorems for some circular-arc graphs (1974) Discrete Math., 7, pp. 167-195
  • Yrysgul, T., A fully dynamic algorithm for recognizing and representing chordal graphs (2007) Perspectives of Systems Informatics, pp. 481-486. , Virbitskaite I., Voronkov A., (eds), Lecture Notes in Comput. Sci., 4378, Springer, Berlin:

Citas:

---------- APA ----------
(2015) . Fully Dynamic Recognition of Proper Circular-Arc Graphs. Algorithmica, 71(4), 904-968.
http://dx.doi.org/10.1007/s00453-013-9835-7
---------- CHICAGO ----------
Soulignac, F.J. "Fully Dynamic Recognition of Proper Circular-Arc Graphs" . Algorithmica 71, no. 4 (2015) : 904-968.
http://dx.doi.org/10.1007/s00453-013-9835-7
---------- MLA ----------
Soulignac, F.J. "Fully Dynamic Recognition of Proper Circular-Arc Graphs" . Algorithmica, vol. 71, no. 4, 2015, pp. 904-968.
http://dx.doi.org/10.1007/s00453-013-9835-7
---------- VANCOUVER ----------
Soulignac, F.J. Fully Dynamic Recognition of Proper Circular-Arc Graphs. Algorithmica. 2015;71(4):904-968.
http://dx.doi.org/10.1007/s00453-013-9835-7