Clique-perfectness and balancedness of some graph classes
A graph is clique-perfect if the maximum size of a clique-independent set (a set of pairwise disjoint maximal cliques) and the minimum size of a clique-transversal set (a set of vertices meeting every maximal clique) coincide for each induced subgraph. A graph is balanced if its clique-matrix contai...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | , , |
| Formato: | Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
Taylor and Francis Ltd.
2014
|
| Acceso en línea: | Registro en Scopus DOI Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 14782caa a22013697a 4500 | ||
|---|---|---|---|
| 001 | PAPER-14683 | ||
| 003 | AR-BaUEN | ||
| 005 | 20230518204515.0 | ||
| 008 | 190411s2014 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-84919438238 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 030 | |a IJCMA | ||
| 100 | 1 | |a Bonomo, F. | |
| 245 | 1 | 0 | |a Clique-perfectness and balancedness of some graph classes |
| 260 | |b Taylor and Francis Ltd. |c 2014 | ||
| 270 | 1 | 0 | |m Safe, M.D.; Instituto de Ciencias, Universidad Nacional de General SarmientoArgentina |
| 506 | |2 openaire |e Política editorial | ||
| 504 | |a Balachandran, V., Nagavamsi, P., Pandu Rangan, C., Clique transversal and clique independence on comparability graphs (1996) Inf. Process. Lett, 58, pp. 181-184 | ||
| 504 | |a Baumann, S., A linear algorithm for the homogeneous decomposition of graphs (1996), Report TUM M9615, Fakultät für Mathematik, Technische Universität München, Munich, Germany; Berge, C., Färbung von Graphen, deren sämtliche beziehungsweise, deren ungerade Kreise starr sind (Zusammenfassung) (1961) Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg, Math.-Naturwiss. Reihe, 10, pp. 114-115 | ||
| 504 | |a Berge, C., Balanced matrices (1972) Math. Program, 2, pp. 19-31 | ||
| 504 | |a Berge, C., Chvátal, V., Introduction, in Topics on Perfect Graphs (1984) North-Holland Mathematics Studies, 88, pp. vii–xiv. , Berge C., Chvátal V., (eds), Noth-Holland, Amsterdam: | ||
| 504 | |a Berge, C., Las Vergnas, M., Sur un théorème du type König pour hypergraphes (1970) Ann. N.Y. Acad. Sci, 175, pp. 32-40 | ||
| 504 | |a Bonomo, F., On subclasses and variations of perfect graphs (2005), Doctoral dissertation, Departamento de Computación, FCEyN, Universidad de Buenos Aires, Buenos Aires, Argentina; Bonomo, F., Durán, G., Groshaus, M., Szwarcfiter, J.L., On clique-perfect and K-perfect graphs (2006) Ars Combin, 80, pp. 97-112 | ||
| 504 | |a Bonomo, F., Durán, G., Lin, M.C., Szwarcfiter, J.L., On balanced graphs (2006) Math. Program, 105, pp. 233-250 | ||
| 504 | |a Bonomo, F., Chudnovsky, M., Durán, G., Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs (2008) Discret. Appl. Math, 156, pp. 1058-1082 | ||
| 504 | |a Bonomo, F., Durán, G., Safe, M.D., Wagler, A.K., On minimal forbidden subgraph characterizations of balanced graphs (2009) Electron. Notes Discret. Math, 35, pp. 41-46 | ||
| 504 | |a Bonomo, F., Durán, G., Soulignac, F., Sueiro, G., Partial characterizations of clique-perfect and coordinated graphs: Superclasses of triangle-free graphs (2009) Discret. Appl. Math, 157, pp. 3511-3518 | ||
| 504 | |a Bonomo, F., Chudnovsky, M., Durán, G., Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs (2009) Discret. Math, 309, pp. 3485-3499 | ||
| 504 | |a Bonomo, F., Durán, G., Safe, M.D., Wagler, A.K., Balancedness of some subclasses of circular-arc graphs (2010) Electron. Notes Discret. Math, 36, pp. 1121-1128 | ||
| 504 | |a Bonomo, F., Durán, G., Safe, M.D., Wagler, A.K., Clique-perfectness of complements of line graphs (2011) Electron. Notes Discret. Math, 37, pp. 327-332 | ||
| 504 | |a Bonomo, F., Durán, G., Safe, M.D., Wagler, A.K., On minimal forbidden subgraph characterizations of balanced graphs (2013) Discret. Appl. Math, 161, pp. 1925-1942 | ||
| 504 | |a Brandstädt, A., Chepoi, V.D., Dragan, F.F., Clique r-domination and clique r-packing problems on dually chordal graphs (1997) SIAM J. Discret. Math, 10, pp. 109-127 | ||
| 504 | |a Buer, B., Möhring, R.H., A fast algorithm for the decomposition of graphs and posets (1983) Math. Oper. Res, 8, pp. 170-184 | ||
| 504 | |a Chang, M., Farber, M., Tuza, Z., Algorithmic aspects of neighbourhood numbers (1993) SIAM J. Discret. Math, 6, pp. 24-29 | ||
| 504 | |a Chang, M.S., Hsieh, S.Y., Chen, G.H., Dynamic programming on distance-hereditary graphs, in Algorithms and Computation (1997) Lecture Notes Computer Science, 1350, pp. 344-353. , Leong H.W., Imai H., Jain S., (eds), 8th International Symposium, ISAAC ’97, Singapore, December 17–19, 1997, Proceedings, Springer, Berlin: | ||
| 504 | |a Chudnovsky, M., Cornuéjols, G.P., Liu, X., Seymour, P.D., Vušković, K., Recognizing Berge graphs (2005) Combinatorica, 25, pp. 143-186 | ||
| 504 | |a Chudnovsky, M., Robertson, N., Seymour, P.D., Thomas, R., The strong perfect graph theorem (2006) Ann. Math, 164, pp. 51-229 | ||
| 504 | |a Chvátal, V., On certain polytopes associated with graphs (1975) J. Combin. Theory Ser. B, 18, pp. 138-154 | ||
| 504 | |a Corneil, D., Perl, Y., Stewart, L., Cographs: Recognition, applications and algorithms (1984) Congr. Numer, 43, pp. 249-258 | ||
| 504 | |a Corneil, D.G., Lerchs, H., Stewart Burlingham, L., Complement reducible graphs (1981) Discret. Appl. Math, 3, pp. 163-174 | ||
| 504 | |a Corneil, D.G., Perl, Y., Stewart, L.K., A linear recognition algorithm for cographs (1985) SIAM J. Comput, 14, pp. 926-934 | ||
| 504 | |a Courcelle, B., A multivariate interlace polynomial and its computation for graphs of bounded clique-width (2008) Electron. J. Comb, 15 | ||
| 504 | |a Courcelle, B., Makowsky, J.A., Rotics, U., Linear time solvable optimization problems on graphs of bounded clique-width (2000) Theory Comput. Syst, 33, pp. 125-150 | ||
| 504 | |a Cournier, A., Habib, M., A new linear algorithm for modular decomposition, in Trees in Algebra and Programming - CAAP’94 (1994) Lecture Notes Computer Science, 787, pp. 68-84. , Tison S., (ed), 19th International Colloquium, Edinburgh, UK, April 11–13, 1994, Proceedings, Springer, Berlin: | ||
| 504 | |a Dahlhaus, E., Manuel, P.D., Miller, M., Maximum h-colourable subgraph problem in balanced graphs (1998) Inf. Process. Lett, 65, pp. 301-303 | ||
| 504 | |a Dahlhaus, E., Gustedt, J., McConnell, R.M., Efficient and practical algorithms for sequential modular decomposition (2001) J. Algorithms, 41, pp. 360-387 | ||
| 504 | |a Durán, G., Lin, M.C., Szwarcfiter, J.L., On clique-transversal and clique-independent sets (2002) Ann. Oper. Res, 116, pp. 71-77 | ||
| 504 | |a Durán, G., Lin, M.C., Mera, S., Szwarcfiter, J.L., Algorithms for clique-independent sets on subclasses of circular-arc graphs (2006) Discret. Appl. Math, 154, pp. 1783-1790 | ||
| 504 | |a Durán, G., Lin, M.C., Mera, S., Szwarcfiter, J.L., Algorithms for finding clique-transversals of graphs (2008) Ann. Oper. Res, 157, pp. 37-45 | ||
| 504 | |a Edmonds, J., Paths, trees, and flowers (1965) Can. J. Math, 17, pp. 449-467 | ||
| 504 | |a Egerváry, J., Matrixok kombinatorikus tulajdonságairól (1931) Mat. Fiz. Lapok, 38, pp. 16-28 | ||
| 504 | |a Erdős, P., Gallai, T., Tuza, Z., Covering the cliques of a graph with vertices (1992) Discret. Math, 108, pp. 279-289 | ||
| 504 | |a Farber, M., Characterizations of strongly chordal graphs (1983) Discret. Math, 43, pp. 173-189 | ||
| 504 | |a Fouquet, J.L., Giakoumakis, V., On semi-P4-sparse graphs (1997) Discret. Math, pp. 277-300 | ||
| 504 | |a Frick, M., Grohe, M., The complexity of first-order and monadic second-order logic revisited (2004) Ann. Pure Appl. Logic, 130, pp. 3-31 | ||
| 504 | |a Fulkerson, D.R., Hoffman, A.J., Oppenheim, R., On balanced matrices, in Pivoting and Extensions: In Honor of A.W. Tucker (1974) Mathematical Programming Study, 1, pp. 120-133. , Balinski M., (ed), North-Holland, Amsterdam: | ||
| 504 | |a Gabow, H., Tarjan, R., Faster scaling algorithms for general graph-matching problems (1991) J. ACM, 38, pp. 815-853 | ||
| 504 | |a Gallai, T., Transitiv orientierbare Graphen (1967) Acta Math. Acad. Sci. Hung, 18, pp. 25-66 | ||
| 504 | |a Giakoumakis, V., Roussel, F., Thuillier, H., On P4-tidy graphs (1997) Discret. Math. Theor. Comput. Sci, 1, pp. 17-41 | ||
| 504 | |a Golumbic, M.C., Trivially perfect graphs (1978) Discret. Math, 24, pp. 105-107 | ||
| 504 | |a Guruswami, V., Pandu Rangan, C., Algorithmic aspects of clique-transversal and clique-independent sets (2000) Discret. Appl. Math, 100, pp. 183-202 | ||
| 504 | |a Hoàng, C.T., Perfect graphs (1985), Ph.D. thesis, School of Computer Science, McGill University, Montreal, Canada; Jamison, B., Olariu, S., A new class of brittle graphs (1989) Stud. Appl. Math, 81, pp. 89-92 | ||
| 504 | |a Jamison, B., Olariu, S., On a unique tree representation for P4-extendible graphs (1991) Discret. Appl. Math, 34, pp. 151-164 | ||
| 504 | |a Kőnig, D., Graphok és Matrixok (1931) Mat. Fiz. Lapok, 38, pp. 116-119 | ||
| 504 | |a Lee, C.M., Chang, M.S., Distance-hereditary graphs are clique-perfect (2006) Discret. Appl. Math, 154, pp. 525-536 | ||
| 504 | |a Lehel, J., Tuza, Z., Neighborhood perfect graphs (1986) Discret. Math, 61, pp. 93-101 | ||
| 504 | |a McConnell, R.M., Spinrad, J.P., Modular decomposition and transitive orientation (1999) Discret. Math, 201, pp. 189-241 | ||
| 504 | |a Meyniel, H., The graphs whose odd cycles have at least two chords, in Topics on Perfect Graphs (1984) North-Holland Mathematics Studies, 88, pp. 115-119. , Berge C., Chvátal V., (eds), Noth-Holland, Amsterdam: | ||
| 504 | |a Olariu, S., Paw-free graphs (1988) Inf. Process. Lett, 28, pp. 53-54 | ||
| 504 | |a Parthasarathy, K., Ravindra, G., The strong perfect-graph conjecture is true for K1, 3-free graphs (1976) J. Combin. Theory Ser. B, 21, pp. 212-223 | ||
| 504 | |a Prisner, E., Hereditary clique-Helly graphs (1993) J. Combin. Math. Combin. Comput, 14, pp. 216-220 | ||
| 504 | |a Sandeep, R.B., Perfectly colorable graphs (2011) Inf. Process. Lett, 111, pp. 960-961 | ||
| 504 | |a Seinsche, D., On a property of the class of n-colorable graphs (1974) J. Combin. Theory Ser. B, 16, pp. 191-193 | ||
| 504 | |a Tedder, M., Corneil1, D., Habib, M., Paul, C., Simpler linear-time modular decomposition via recursive factorizing permutations, in Automata, Languages and Programming (2008) Lecture Notes Computer Science, 5125. , Aceto L., Damgård I., Goldberg L.A., Halldórsson M.M., Ingólfsdóttir A., Walukiewicz I., (eds), 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7–11, 2008, Proceedings, Part I, Springer, Berlin: | ||
| 504 | |a Tsukiyama, S., Idle, M., Ariyoshi, H., Shirakawa, Y., A new algorithm for generating all the maximal independent sets (1977) SIAM J. Comput, 6, pp. 505-517 | ||
| 504 | |a Tucker, A., The strong perfect graph conjecture for planar graphs (1973) Can. J. Math, 25, pp. 103-114 | ||
| 504 | |a Tucker, A., Coloring perfect (K4−e)-free graphs (1987) J. Combin. Theory Ser. B, 42, pp. 313-318 | ||
| 504 | |a West, D.B., (2001) Introduction to Graph Theory, , 2nd ed., Prentice-Hall, Upper Saddle River, NJ: | ||
| 504 | |a Zambelli, G., A polynomial recognition algorithm for balanced matrices (2005) J. Combin. Theory Ser. B, 95, pp. 49-67 | ||
| 520 | 3 | |a A graph is clique-perfect if the maximum size of a clique-independent set (a set of pairwise disjoint maximal cliques) and the minimum size of a clique-transversal set (a set of vertices meeting every maximal clique) coincide for each induced subgraph. A graph is balanced if its clique-matrix contains no square submatrix of odd size with exactly two ones per row and column. In this work, we give linear-time recognition algorithms and minimal forbidden induced subgraph characterizations of clique-perfectness and balancedness of P4-tidy graphs and a linear-time algorithm for computing a maximum clique-independent set and a minimum clique-transversal set for any P4-tidy graph. We also give a minimal forbidden induced subgraph characterization and a linear-time recognition algorithm for balancedness of paw-free graphs. Finally, we show that clique-perfectness of diamond-free graphs can be decided in polynomial time by showing that a diamond-free graph is clique-perfect if and only if it is balanced. © 2014, © 2014 Taylor & Francis. |l eng | |
| 536 | |a Detalles de la financiación: Fondo Nacional de Desarrollo Científico, Tecnológico y de Innovación Tecnológica, 1110797 | ||
| 536 | |a Detalles de la financiación: Secretaría de Ciencia y Técnica, Universidad de Buenos Aires, 20020100100980 | ||
| 536 | |a Detalles de la financiación: PICT-2012-1324 | ||
| 536 | |a Detalles de la financiación: PIP 112-200901-00178 | ||
| 536 | |a Detalles de la financiación: The authors are indebted to the referees for insightful comments, corrections, and suggestions that helped to improve this paper. The first three named authors were partially supported by UBACyT Grant 20020100100980, CONICET PIP 112-200901-00178, and ANPCyT PICT-2012-1324 (Argentina). G. Durán was also partially supported by FONDECyT Grant 1110797 and Millennium Science Institute ‘Complex Engineering Systems’ (Chile). | ||
| 593 | |a CONICET and Departamento de Computación, FCEN, Universidad de Buenos Aires, Buenos Aires, Argentina | ||
| 593 | |a CONICET, Instituto de Cálculo, and Departamento de Matemática, FCEN, Universidad de Buenos Aires, Buenos Aires, Argentina | ||
| 593 | |a Departamento de Ingeniería Industrial, FCFM, Universidad de Chile, Santiago de Chile, Chile | ||
| 593 | |a Instituto de Ciencias, Universidad Nacional de General Sarmiento, Los Polvorines, Argentina | ||
| 593 | |a CNRS and LIMOS, UFR Sciences et Techniques, Université Blaise Pascal, Aubiére, France | ||
| 690 | 1 | 0 | |a BALANCED GRAPHS |
| 690 | 1 | 0 | |a CLIQUE-PERFECT GRAPHS |
| 690 | 1 | 0 | |a DIAMOND-FREE GRAPHS |
| 690 | 1 | 0 | |a P4-TIDY GRAPHS |
| 690 | 1 | 0 | |a PAW-FREE GRAPHS |
| 690 | 1 | 0 | |a RECOGNITION ALGORITHMS |
| 690 | 1 | 0 | |a CLUSTERING ALGORITHMS |
| 690 | 1 | 0 | |a DIAMONDS |
| 690 | 1 | 0 | |a GRAPHIC METHODS |
| 690 | 1 | 0 | |a POLYNOMIAL APPROXIMATION |
| 690 | 1 | 0 | |a BALANCED GRAPHS |
| 690 | 1 | 0 | |a DIAMOND-FREE GRAPHS |
| 690 | 1 | 0 | |a FREE GRAPHS |
| 690 | 1 | 0 | |a PERFECT GRAPH |
| 690 | 1 | 0 | |a RECOGNITION ALGORITHM |
| 690 | 1 | 0 | |a GRAPH THEORY |
| 700 | 1 | |a Durán, G. | |
| 700 | 1 | |a Safe, M.D. | |
| 700 | 1 | |a Wagler, A.K. | |
| 773 | 0 | |d Taylor and Francis Ltd., 2014 |g v. 91 |h pp. 2118-2141 |k n. 10 |p Int J Comput Math |x 00207160 |w (AR-BaUEN)CENRE-5228 |t International Journal of Computer Mathematics | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-84919438238&doi=10.1080%2f00207160.2014.881994&partnerID=40&md5=8c097ac0130f332b08074a5b647ddabc |y Registro en Scopus |
| 856 | 4 | 0 | |u https://doi.org/10.1080/00207160.2014.881994 |y DOI |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_00207160_v91_n10_p2118_Bonomo |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00207160_v91_n10_p2118_Bonomo |y Registro en la Biblioteca Digital |
| 961 | |a paper_00207160_v91_n10_p2118_Bonomo |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 75636 | ||