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