A faster algorithm for the cluster editing problem on proper interval graphs

Mostrar otras versiones (1)

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.

Guardado en:
Detalles Bibliográficos
Autor principal: Lin, M.C
Otros Autores: Soulignac, F.J, Szwarcfiter, J.L
Formato: Capítulo de libro
Lenguaje:Inglés
Publicado: Elsevier 2015
Acceso en línea:Registro en Scopus
DOI
Handle
Registro en la Biblioteca Digital
Aporte de:Registro referencial: Solicitar el recurso aquí
Biblioteca Central Dr. Luis F. Leloir (FCEN) de Universidad de Buenos Aires
LEADER 06033caa a22007577a 4500
001 PAPER-24661
003 AR-BaUEN
005 20230518205634.0
008 190411s2015 xx ||||fo|||| 00| 0 eng|d
024 7 |2 scopus  |a 2-s2.0-84938313329 
040 |a Scopus  |b spa  |c AR-BaUEN  |d AR-BaUEN 
030 |a IFPLA 
100 1 |a Lin, M.C. 
245 1 2 |a A faster algorithm for the cluster editing problem on proper interval graphs 
260 |b Elsevier  |c 2015 
270 1 0 |m Lin, M.C.; CONICET, Departamento de Computación, Universidad de Buenos AiresArgentina 
506 |2 openaire  |e Política editorial 
504 |a Křivánek, M., Morávek, J., NP-hard problems in hierarchical-tree clustering (1986) Acta Inform., 23 (3), pp. 311-323 
504 |a Shamir, R., Sharan, R., Tsur, D., Cluster graph modification problems (2004) Discrete Appl. Math., 144 (1-2), pp. 173-182 
504 |a Cai, L., Fixed-parameter tractability of graph modification problems for hereditary properties (1996) Inf. Process. Lett., 58 (4), pp. 171-176 
504 |a Chen, J., Meng, J., A 2k kernel for the cluster editing problem (2012) J. Comput. Syst. Sci., 78 (1), pp. 211-220 
504 |a 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 
504 |a Damaschke, P., Cluster editing with locally bounded modifications revisited (2013) Combinatorial Algorithms Lecture Notes in Computer Science, 8288, pp. 433-437. , Springer Heidelberg 
504 |a Komusiewicz, C., Uhlmann, J., Cluster editing with locally bounded modifications (2012) Discrete Appl. Math., 160 (15), pp. 2259-2270 
504 |a Böcker, S., A golden ratio parameterized algorithm for cluster editing (2012) J. Discrete Algorithms, 16, pp. 79-89 
504 |a Böcker, S., Briesemeister, S., Klau, G.W., Exact algorithms for cluster editing: Evaluation and experiments (2011) Algorithmica, 60 (2), pp. 316-334 
504 |a 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 
504 |a Damaschke, P., Fixed-parameter enumerability of cluster editing and related problems (2010) Theory Comput. Syst., 46 (2), pp. 261-283 
504 |a 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 
504 |a 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 
504 |a Mannaa, B., Cluster editing problem for points on the real line: A polynomial time algorithm (2010) Inf. Process. Lett., 110 (21), pp. 961-965 
504 |a 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 
504 |a 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 
520 3 |a 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.  |l eng 
536 |a Detalles de la financiación: Conselho Nacional de Desenvolvimento Científico e Tecnológico, CNPq 
536 |a Detalles de la financiación: Coordenação de Aperfeiçoamento de Pessoal de Nível Superior 
536 |a Detalles de la financiación: 2013-2205, 2010-1970 
536 |a Detalles de la financiación: Secretaría de Ciencia y Técnica, Universidad de Buenos Aires, 20020120100058 
536 |a Detalles de la financiación: We thank the anonymous reviewers for their helpful comments. The first author was partially supported by UBACyT Grant 20020120100058 , and PICT ANPCyT Grants 2010-1970 and 2013-2205 . The second author was partially supported by PICT ANPCyT Grants 2010-1970 and 2013-2205 . The third author was partially supported by CNPq and CAPES , research agencies. 
593 |a CONICET, Departamento de Computación, Universidad de Buenos Aires, Argentina 
593 |a CONICET, Departamento de Ciencia y Tecnología, Universidad Nacional de Quilmes, Argentina 
593 |a Instituto de Matemática, NCE, COPPE, Universidade Federal Do Rio de Janeiro, Brazil 
593 |a Instituto Nacional de Metrologia, Qualidade e Tecnologia, Brazil 
690 1 0 |a CLUSTER EDITING PROBLEM 
690 1 0 |a GRAPH ALGORITHMS 
690 1 0 |a LINEAR SPACE ALGORITHM 
690 1 0 |a PROPER INTERVAL MODELS 
690 1 0 |a ALGORITHMS 
690 1 0 |a CLUSTER EDITING 
690 1 0 |a GRAPH ALGORITHMS 
690 1 0 |a INTERVAL MODELS 
690 1 0 |a LINEAR SPACE ALGORITHMS 
690 1 0 |a LINEAR SPACES 
690 1 0 |a PROPER INTERVAL GRAPHS 
690 1 0 |a TIME ALGORITHMS 
690 1 0 |a CLUSTERING ALGORITHMS 
700 1 |a Soulignac, F.J. 
700 1 |a Szwarcfiter, J.L. 
773 0 |d Elsevier, 2015  |g v. 115  |h pp. 913-916  |k n. 12  |p Inf. Process. Lett.  |x 00200190  |w (AR-BaUEN)CENRE-1599  |t Information Processing Letters 
856 4 1 |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-84938313329&doi=10.1016%2fj.ipl.2015.07.009&partnerID=40&md5=62eb54e26643b60ba12a67e9a5ea28f1  |y Registro en Scopus 
856 4 0 |u https://doi.org/10.1016/j.ipl.2015.07.009  |y DOI 
856 4 0 |u https://hdl.handle.net/20.500.12110/paper_00200190_v115_n12_p913_Lin  |y Handle 
856 4 0 |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00200190_v115_n12_p913_Lin  |y Registro en la Biblioteca Digital 
961 |a paper_00200190_v115_n12_p913_Lin  |b paper  |c PE 
962 |a info:eu-repo/semantics/article  |a info:ar-repo/semantics/artículo  |b info:eu-repo/semantics/publishedVersion 
999 |c 85614 

Ejemplares similares