Navegar

Colección

Datos Estadísticas

Artículo

La versión final de este artículo es de uso interno. El editor solo permite incluir en el repositorio el artículo en su versión post-print. Por favor, si usted la posee enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

A {0, 1}-matrix is balanced if it contains no square submatrix of odd order with exactly two 1's per row and per column. Balanced matrices lead to ideal formulations for both set packing and set covering problems. Balanced graphs are those graphs whose clique-vertex incidence matrix is balanced. While a forbidden induced subgraph characterization of balanced graphs is known, there is no such characterization by minimal forbidden induced subgraphs. In this work we provide minimal forbidden induced subgraph characterizations of balanced graphs restricted to some graph classes which also lead to polynomial time or even linear time recognition algorithms within the corresponding subclasses. © 2009 Elsevier B.V. All rights reserved.

Registro:

Documento: Artículo
Título:On minimal forbidden subgraph characterizations of balanced graphs
Autor:Bonomo, F.; Durán, G.; Safe, M.D.; Wagler, A.K.
Filiación:CONICET, Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Buenos Aires, Argentina
CONICET, Departamento de Matemática, Facultad de Ciencias Exactas y Naturales, Buenos Aires, Argentina
Departamento de Ingeniería Industrial, Facultad de Ciencias Físicas y Matemáticas, Universidad de Chile, Santiago, Chile
Institut für Mathematische Optimierung, Fakultät für Mathematik, Otto-von-Guericke-Universität Magdeburg, Germany
Palabras clave:balanced graphs; line graphs; P4-tidy graphs; paw-free graphs; perfect
Año:2009
Volumen:35
Número:C
Página de inicio:41
Página de fin:46
DOI: http://dx.doi.org/10.1016/j.endm.2009.11.008
Título revista:Electronic Notes in Discrete Mathematics
Título revista abreviado:Electron. Notes Discrete Math.
ISSN:15710653
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v35_nC_p41_Bonomo

Referencias:

  • Berge, C., Balanced matrices (1972) Math. Program., 2, pp. 19-31
  • Berge, C., Motivation and history of some of my conjectures (1997) Discrete Math., 165-166, pp. 61-70
  • Bonomo, F., Durán, G., Lin, M.C., Szwarcfiter, J.L., On balanced graphs (2006) Math. Program., 105, pp. 233-250
  • Chudnovsky, M., Cornuéjols, G.P., Liu, X., Seymour, P.D., Vušković, K., Recognizing Berge graphs (2005) Combinatorica, 25, pp. 143-186
  • Chudnovsky, M., Robertson, N., Seymour, P.D., Thomas, R., The strong perfect graph theorem (2006) Ann. Math., 164, pp. 51-229
  • Chvátal, V., On certain polytopes associated with graphs (1975) J. Combin. Theory Ser. B, 18, pp. 138-154
  • Dahlhaus, E., Manuel, P.D., Miller, M., Maximum h-colourable subgraph problem in balanced graphs (1998) Inform. Process. Lett., 65, pp. 301-303
  • Fulkerson, D.R., Hoffman, A.J., Oppenheim, R., On balanced matrices (1974) Math. Program. Study, 1, pp. 120-133. , Pivoting and Extensions: In honor of A.W. Tucker. Balinski M. (Ed), North-Holland, Amsterdam
  • Giakoumakis, V., Roussel, F., Thuillier, H., On P4-tidy graphs (1997) Discrete Math. Theor. Comput. Sci., 1, pp. 17-41
  • Lovász, L., Normal hypergraphs and the perfect graph conjecture (1972) Discrete Math., 2, pp. 253-267
  • Prisner, E., Hereditary clique-Helly graphs (1993) J. Combin. Math. Combin. Comput., 14, pp. 216-220
  • Trotter, L.E., Line perfect graphs (1977) Math. Program., 12, pp. 255-259
  • Zambelli, G., A polynomial recognition algorithm for balanced matrices (2005) J. Combin. Theory Ser. B, 95, pp. 49-67

Citas:

---------- APA ----------
Bonomo, F., Durán, G., Safe, M.D. & Wagler, A.K. (2009) . On minimal forbidden subgraph characterizations of balanced graphs. Electronic Notes in Discrete Mathematics, 35(C), 41-46.
http://dx.doi.org/10.1016/j.endm.2009.11.008
---------- CHICAGO ----------
Bonomo, F., Durán, G., Safe, M.D., Wagler, A.K. "On minimal forbidden subgraph characterizations of balanced graphs" . Electronic Notes in Discrete Mathematics 35, no. C (2009) : 41-46.
http://dx.doi.org/10.1016/j.endm.2009.11.008
---------- MLA ----------
Bonomo, F., Durán, G., Safe, M.D., Wagler, A.K. "On minimal forbidden subgraph characterizations of balanced graphs" . Electronic Notes in Discrete Mathematics, vol. 35, no. C, 2009, pp. 41-46.
http://dx.doi.org/10.1016/j.endm.2009.11.008
---------- VANCOUVER ----------
Bonomo, F., Durán, G., Safe, M.D., Wagler, A.K. On minimal forbidden subgraph characterizations of balanced graphs. Electron. Notes Discrete Math. 2009;35(C):41-46.
http://dx.doi.org/10.1016/j.endm.2009.11.008