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 develop a linear-space O(n+m) time algorithm to solve the cluster editing problem for proper interval models, where n and m are the number of vertices and edges of the represented graph. © 2015 Elsevier B.V. All rights reserved.

Registro:

Documento: Artículo
Título:A faster algorithm for the cluster editing problem on proper interval graphs
Autor:Lin, M.C.; Soulignac, F.J.; Szwarcfiter, J.L.
Filiación:CONICET, Departamento de Computación, Universidad de Buenos Aires, Argentina
CONICET, Departamento de Ciencia y Tecnología, Universidad Nacional de Quilmes, Argentina
Instituto de Matemática, NCE, COPPE, Universidade Federal Do Rio de Janeiro, Brazil
Instituto Nacional de Metrologia, Qualidade e Tecnologia, Brazil
Palabras clave:Cluster editing problem; Graph algorithms; Linear space algorithm; Proper interval models; Algorithms; Cluster editing; Graph algorithms; Interval models; Linear space algorithms; Linear spaces; Proper interval graphs; Time algorithms; Clustering algorithms
Año:2015
Volumen:115
Número:12
Página de inicio:913
Página de fin:916
DOI: http://dx.doi.org/10.1016/j.ipl.2015.07.009
Título revista:Information Processing Letters
Título revista abreviado:Inf. Process. Lett.
ISSN:00200190
CODEN:IFPLA
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00200190_v115_n12_p913_Lin

Referencias:

  • Křivánek, M., Morávek, J., NP-hard problems in hierarchical-tree clustering (1986) Acta Inform., 23 (3), pp. 311-323
  • Shamir, R., Sharan, R., Tsur, D., Cluster graph modification problems (2004) Discrete Appl. Math., 144 (1-2), pp. 173-182
  • Cai, L., Fixed-parameter tractability of graph modification problems for hereditary properties (1996) Inf. Process. Lett., 58 (4), pp. 171-176
  • Chen, J., Meng, J., A 2k kernel for the cluster editing problem (2012) J. Comput. Syst. Sci., 78 (1), pp. 211-220
  • Protti, F., Dantas da Silva, M., Szwarcfiter, J.L., Applying modular decomposition to parameterized cluster editing problems (2009) Theory Comput. Syst., 44 (1), pp. 91-104
  • Damaschke, P., Cluster editing with locally bounded modifications revisited (2013) Combinatorial Algorithms Lecture Notes in Computer Science, 8288, pp. 433-437. , Springer Heidelberg
  • Komusiewicz, C., Uhlmann, J., Cluster editing with locally bounded modifications (2012) Discrete Appl. Math., 160 (15), pp. 2259-2270
  • Böcker, S., A golden ratio parameterized algorithm for cluster editing (2012) J. Discrete Algorithms, 16, pp. 79-89
  • Böcker, S., Briesemeister, S., Klau, G.W., Exact algorithms for cluster editing: Evaluation and experiments (2011) Algorithmica, 60 (2), pp. 316-334
  • Bastos, L., Satoru Ochi, L., Protti, F., Subramanian, A., Martins, I.C., Pinheiro, R.G.S., Efficient algorithms for cluster editing (2014) J. Comb. Optim., , available online
  • Damaschke, P., Fixed-parameter enumerability of cluster editing and related problems (2010) Theory Comput. Syst., 46 (2), pp. 261-283
  • Fellows, M.R., Guo, J., Komusiewicz, C., Niedermeier, R., Uhlmann, J., Graph-based data clustering with overlaps (2011) Discrete Optim., 8 (1), pp. 2-17
  • Böcker, S., Baumbach, J., Cluster editing (2013) The Nature of Computation. Logic, Algorithms, Applications, 7921, pp. 33-44. , Lecture Notes in Computer Science Springer Heidelberg
  • Mannaa, B., Cluster editing problem for points on the real line: A polynomial time algorithm (2010) Inf. Process. Lett., 110 (21), pp. 961-965
  • Roberts, F.S., Indifference graphs (1969) Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf.), pp. 139-146. , Ann Arbor, Mich., 1968 Academic Press 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

Citas:

---------- APA ----------
Lin, M.C., Soulignac, F.J. & Szwarcfiter, J.L. (2015) . A faster algorithm for the cluster editing problem on proper interval graphs. Information Processing Letters, 115(12), 913-916.
http://dx.doi.org/10.1016/j.ipl.2015.07.009
---------- CHICAGO ----------
Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L. "A faster algorithm for the cluster editing problem on proper interval graphs" . Information Processing Letters 115, no. 12 (2015) : 913-916.
http://dx.doi.org/10.1016/j.ipl.2015.07.009
---------- MLA ----------
Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L. "A faster algorithm for the cluster editing problem on proper interval graphs" . Information Processing Letters, vol. 115, no. 12, 2015, pp. 913-916.
http://dx.doi.org/10.1016/j.ipl.2015.07.009
---------- VANCOUVER ----------
Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L. A faster algorithm for the cluster editing problem on proper interval graphs. Inf. Process. Lett. 2015;115(12):913-916.
http://dx.doi.org/10.1016/j.ipl.2015.07.009