Artículo
Bonomo, F.; De Figueiredo, C.M.H.; Durán, G.; Grippo, L.N.; Safe, M.D.; Szwarcfiter, J.L. "On probe 2-clique graphs and probe diamond-free graphs" (2015) Discrete Mathematics and Theoretical Computer Science. 17(1):187-200
Estamos trabajando para incorporar este artículo al repositorio
Consulte la política de Acceso Abierto del editor
Abstract:
Given a class G of graphs, probe G graphs are defined as follows. A graph G is probe G if there exists a partition of its vertices into a set of probe vertices and a stable set of nonprobe vertices in such a way that non-edges of G, whose endpoints are nonprobe vertices, can be added so that the resulting graph belongs to G. We investigate probe 2-clique graphs and probe diamond-free graphs. For probe 2-clique graphs, we present a polynomial-time recognition algorithm. Probe diamond-free graphs are characterized by minimal forbidden induced subgraphs. As a by-product, it is proved that the class of probe block graphs is the intersection between the classes of chordal graphs and probe diamond-free graphs. © 2015 Discrete Mathematics and Theoretical Computer Science (DMTCS).
Registro:
| Documento: | Artículo |
| Título: | On probe 2-clique graphs and probe diamond-free graphs |
| Autor: | Bonomo, F.; De Figueiredo, C.M.H.; Durán, G.; Grippo, L.N.; Safe, M.D.; Szwarcfiter, J.L. |
| Filiación: | CONICET, Argentina COPPE, Universidade Federal do Rio de Janeiro, Brazil NCE, Universidade Federal do Rio de Janeiro, Brazil Depto. de Computación, FCEN, Universidad de Buenos Aires, Buenos Aires, Argentina Depto. de Matemática, Instituto de Cálculo, Universidad de Buenos Aires, Buenos Aires, Argentina Depto. de Ingeniería Industrial, FCFM, Universidad de Chile, Santiago, Chile Instituto de Ciencias, Universidad Nacional de General Sarmiento, Los Polvorines, Argentina |
| Palabras clave: | 2-clique graphs; Diamond-free graphs; Probe graphs; Diamonds; Graphic methods; Polynomial approximation; Probes; 2-clique graphs; Block graphs; Chordal graphs; Diamond-free graphs; Forbidden induced subgraphs; Polynomial-time; Probe graph; Recognition algorithm; Graph theory |
| Año: | 2015 |
| Volumen: | 17 |
| Número: | 1 |
| Página de inicio: | 187 |
| Página de fin: | 200 |
| Título revista: | Discrete Mathematics and Theoretical Computer Science |
| Título revista abreviado: | Discrete Math. Theor. Comput. Sci. |
| ISSN: | 14627264 |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v17_n1_p187_Bonomo |
Referencias:
- Bayer, D., Le, V.B., De Ridder, H.N., Probe threshold and probe trivially perfect graphs (2009) Theoretical Computer Science, 410 (47-49), pp. 4812-4822
- Berry, A., Golumbic, M.C., Lipshteyn, M., Recognizing chordal probe graphs and cyclebicolorable graphs (2007) SIAM Journal on Discrete Mathematics, 21 (3), pp. 573-591
- Brown, D.E., Langley, L.J., Probe interval orders (2009) The Mathematics of Preference Choice and Order, Essays in Honor of P. C. Fishburn, pp. 313-322. , Brams, Gehrlein, and Roberts, editors, Springer Berlin Heidelberg
- Chandler, D.B., Chang, M.-S., Kloks, T., Liu, J., Peng, S.-L., Recognition of probe cographs and partitioned probe distance hereditary graphs (2006) Lecture Notes in Computer Science, 4041, pp. 267-278. , S.-W. Cheng and C. K. Poon, editors, Proceedings of the Second International Conference on Algorithmic Aspects in Information and Management, AAIM 2006, Hong Kong, China, June 20-22, 2006, Springer
- Chang, M.-S., Hung, L.-J., Kloks, T., Peng, S.-L., Block-graph width (2011) Theoretical Computer Science, 412 (23), pp. 2496-2502
- Chang, M.-S., Hung, L.-J., Rossmanith, P., Recognition of probe distance-hereditary graphs (2013) Discrete Applied Mathematics, 161 (3), pp. 336-348
- L, J., Chang, G.J., Kloks, A.J.J., Peng, S.-L., The pigs full monty - A floor show of minimal separators, in stacs 2005 (2005) Lecture Notes in Computer Science, 3404, pp. 521-532. , proceedings. Springer
- Golumbic, M.C., Algorithmic graph theory and perfect graphs (2004) Annals of Discrete Mathematics, 57. , Elsevier, Amsterdam, second edition
- Golumbic, M.C., Lipshteyn, M., Chordal probe graphs (2004) Discrete Applied Mathematics, 143 (1-3), pp. 221-237
- Golumbic, M.C., Maffray, F., Morel, G., A characterization of chain probe graphs (2011) Annals of Operations Research, 188, pp. 175-183
- Grippo, L.N., (2011) Structural Characterizations of Intersection Graphs, , PhD thesis, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Argentina
- Hell, P., Huang, J., Interval bigraphs and circular arc graphs (2004) Journal of Graph Theory, 46 (4), pp. 313-327
- Johnson, J.L., Spinrad, J.P., A polynomial time recognition algorithm for probe interval graphs (2001) Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (Washington,DC, 2001), , SIAM
- Kay, D.C., Chartrand, G., A characterization of certain Ptolemaic graphs (1965) Canadian Journal of Mathematics, 17, pp. 342-346
- Le, V., Peng, S.-L., Characterizing and recognizing probe block graphs (2013) Smart Innovation, Systems and Technologies, 20, pp. 7-13. , R.-S. Chang, L. C. Jain, and S.-L. Peng, editors, Proceedings of the Workshop on Algorithms, Bioinformatics, and Computation Theory of the International Computer Symposium, ICS 2012, Hualien, Taiwan, December 12-14, 2012, Springer Berlin Heidelberg
- McConnell, R.M., Spinrad, J., Construction of probe interval models (2002) Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 6-8, 2002, San Francisco, CA, USA, pp. 866-875
- Spinrad, J., Circular-arc graphs with clique cover number two (1988) J. Comb. Theory, Ser. B, 44 (3), pp. 300-306
- West, D.B., (1996) Introduction to Graph Theory, , Prentice Hall Inc., Upper Saddle River, NJ
- Zhang, P., Schon, E., Fischer, S., C, E., Weiss, J., Kistler, S., Bourne, P., An algorithm based on graph theory for ghe assembly of contigs in physical mapping of DNA (1994) Computer Applications in the Biosciences, 10 (3), pp. 309-317
Citas:
---------- APA ----------
Bonomo, F., De Figueiredo, C.M.H., Durán, G., Grippo, L.N., Safe, M.D. & Szwarcfiter, J.L. (2015) . On probe 2-clique graphs and probe diamond-free graphs. Discrete Mathematics and Theoretical Computer Science, 17(1), 187-200.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v17_n1_p187_Bonomo [ ]
---------- CHICAGO ----------
Bonomo, F., De Figueiredo, C.M.H., Durán, G., Grippo, L.N., Safe, M.D., Szwarcfiter, J.L. "On probe 2-clique graphs and probe diamond-free graphs" . Discrete Mathematics and Theoretical Computer Science 17, no. 1 (2015) : 187-200.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v17_n1_p187_Bonomo [ ]
---------- MLA ----------
Bonomo, F., De Figueiredo, C.M.H., Durán, G., Grippo, L.N., Safe, M.D., Szwarcfiter, J.L. "On probe 2-clique graphs and probe diamond-free graphs" . Discrete Mathematics and Theoretical Computer Science, vol. 17, no. 1, 2015, pp. 187-200.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v17_n1_p187_Bonomo [ ]
---------- VANCOUVER ----------
Bonomo, F., De Figueiredo, C.M.H., Durán, G., Grippo, L.N., Safe, M.D., Szwarcfiter, J.L. On probe 2-clique graphs and probe diamond-free graphs. Discrete Math. Theor. Comput. Sci. 2015;17(1):187-200.Available from: https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v17_n1_p187_Bonomo [ ]
