Navegar

Colección

Datos Estadísticas

Artículo

Bonomo, F.; Durán, G.; Lin, M.C.; Szwarcfiter, J.L. "On balanced graphs" (2006) Mathematical Programming. 105(2-3):233-250
La versión final de este artículo es de uso interno de la institución.
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

Berge defined a hypergraph to be balanced if its incidence matrix is balanced. We consider this concept applied to graphs, and call a graph to be balanced when its clique matrix is balanced. Characterizations of balanced graphs by forbidden subgraphs and by clique subgraphs are proved in this work. Using properties of domination we define four subclasses of balanced graphs. Two of them are characterized by 0-1 matrices and can be recognized in polynomial time. Furthermore, we propose polynomial time combinatorial algorithms for the problems of stable set, clique-independent set and clique-transversal for one of these subclasses of balanced graphs. Finally, we analyse the behavior of balanced graphs and these four subclasses under the clique graph operator.

Registro:

Documento: Artículo
Título:On balanced graphs
Autor:Bonomo, F.; Durán, G.; Lin, M.C.; Szwarcfiter, J.L.
Filiación:Dep. de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina
Dep. de Ingeniería Industrial, Facultad de Ciencias Físicas y Matemáticas, Universidad de Chile, Santiago, Chile
Instituto de Matemática, NCE and COPPE, Universidade Federal Do Rio de Janeiro, Caixa Postal 2324, 20001-970 Rio de Janeiro, RJ, Brazil
Palabras clave:0-1 matrices; Algorithms; Balanced graphs; Balanced hypergraphs; Clique graphs; Domination; Algorithms; Graph theory; Matrix algebra; Polynomials; Balanced graphs; Balanced hypergraphs; Clique graphs; Domination; Mathematical programming
Año:2006
Volumen:105
Número:2-3
Página de inicio:233
Página de fin:250
DOI: http://dx.doi.org/10.1007/s10107-005-0651-y
Título revista:Mathematical Programming
Título revista abreviado:Math. Program.
ISSN:00255610
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00255610_v105_n2-3_p233_Bonomo

Referencias:

  • Anstee, R., Farber, M., Characterizations of totally balanced matrices (1984) J. Algorithms, 5, pp. 215-230
  • Berge, C., Les problemes de colorations en théorie des graphes (1960) Publ. Inst. Stat. Univ. Paris, 9, pp. 123-160
  • Berge, C., Sur certains hypergraphes généralisant les graphes biparties (1970) Combinatorial Theory and Applications, pp. 119-133. , P. Erdös, A. Rényi, V. Sós (eds.). North-Holland, Amsterdam
  • Berge, C., Balanced matrices (1972) Math. Program., 2, pp. 19-31
  • Berge, C., Notes sur les bonnes colorations d'un hypergraphe (1973) Cah. Cent. Etud. Rech. Oper., 15, pp. 219-223
  • 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-110
  • Cameron, K., Edmonds, J., Existentially polytime theorems (1990) DIMACS, Ser. Discrete Math. Theor. Comput. Sci., 1, pp. 83-100
  • Chvátal, V., On certain polytopes associated with graphs (1975) J. Comb. Theory, Ser. B, 18, pp. 138-154
  • Conforti, M., (2004), Personal communication; Conforti, M., Cornuéjols, G., Rao, R., Decomposition of balanced matrices (1999) J. Comb. Theory, Ser. B, 77, pp. 292-406
  • Conforti, M., Cornuéjols, G., Vušković, K., Balanced matrices Discrete Math., , To appear
  • Cornuéjols, G., (2001) Combinatorial Optimization: Packing and Covering, , SIAM, Philadelphia
  • Dahlhaus, E., Manuel, P., Miller, M., Maximum h-colourable subgraph problem in balanced graphs (1998) Inf. Process. Lett., 65, pp. 301-303
  • Duchet, P., Hypergraphs (1995) Handbook of Combinatorics, pp. 381-432. , R. Graham, M. Grötschel, L. Lovász (eds.). Elsevier, Amsterdam
  • Escalante, F., Über iterierte clique-graphen (1973) Abh. Math. Semin. Univ. Hamb., 39, pp. 59-68
  • Farber, M., Characterizations of strongly chordal graphs (1983) Discrete Math., 43, pp. 173-189
  • Fulkerson, D., Hoffman, A., Oppenheim, R., On balanced matrices (1974) Math. Program., 1, pp. 120-132
  • Golumbic, M., Algorithmic graph theory and perfect graphs (2004) Ann. Discrete Math., 57. , second edn. North-Holland, Amsterdam
  • Grötschel, M., Lovász, L., Schrijver, A., The ellipsoid method and its consequences in combinatorial optimization (1981) Combinatorica, 1, pp. 169-197
  • Guruswami, V., Pandu Rangan, C., Algorithmic aspects of clique-transversal and clique-independent sets (2000) Discrete Appl. Math., 100, pp. 183-202
  • Hamelink, R., A partial characterization of clique graphs (1968) J. Comb. Theory, Ser. B, 5, pp. 192-197
  • Hopcroft, J., Karp, R., An n5/2 algorithm for maximum matchings in bipartite graphs (1973) SIAM J. Comput., 2, pp. 225-231
  • Hsu, W., Nemhauser, G., Algorithms for minimum covering by cliques and maximum clique in claw-free perfect graphs (1981) Discrete Math., 37, pp. 181-191
  • Lehel, J., Tuza, Z., Neighborhood perfect graphs (1986) Discrete Math., 61, pp. 93-101
  • Lubiw, A., (1985) Orderings and Some Combinatorial Optimization Problems with Geometric Applications, , Ph.D. thesis, Department of Computer Science, University of Toronto, Toronto
  • Prisner, E., Hereditary clique-Helly graphs (1993) J. Comb. Math. Comb. Comput., 14, pp. 216-220
  • Protti, F., Szwarcflter, J., Clique-inverse graphs of bipartite graphs (2002) J. Comb. Math. Comb. Comput., 40, pp. 193-203
  • Sbihi, N., Algorithmes de recherche d'un stable de cardinalite maximum dans un graphe sans etoile (1980) Discrete Math., 29, pp. 53-76
  • Szwarcfiter, J., A survey on Clique Graphs (2003) Recent Advances in Algorithms and Combinatorics, pp. 109-136. , C. Linhares Sales, B. Reed (eds.). Springer-Verlag, New York
  • Tsukiyama, S., Idle, M., Ariyoshi, H., Shirakawa, Y., A new algorithm for generating all the maximal independent sets (1977) SIAM J. Comput., 6 (3), pp. 505-517

Citas:

---------- APA ----------
Bonomo, F., Durán, G., Lin, M.C. & Szwarcfiter, J.L. (2006) . On balanced graphs. Mathematical Programming, 105(2-3), 233-250.
http://dx.doi.org/10.1007/s10107-005-0651-y
---------- CHICAGO ----------
Bonomo, F., Durán, G., Lin, M.C., Szwarcfiter, J.L. "On balanced graphs" . Mathematical Programming 105, no. 2-3 (2006) : 233-250.
http://dx.doi.org/10.1007/s10107-005-0651-y
---------- MLA ----------
Bonomo, F., Durán, G., Lin, M.C., Szwarcfiter, J.L. "On balanced graphs" . Mathematical Programming, vol. 105, no. 2-3, 2006, pp. 233-250.
http://dx.doi.org/10.1007/s10107-005-0651-y
---------- VANCOUVER ----------
Bonomo, F., Durán, G., Lin, M.C., Szwarcfiter, J.L. On balanced graphs. Math. Program. 2006;105(2-3):233-250.
http://dx.doi.org/10.1007/s10107-005-0651-y