On minimal forbidden subgraph characterizations of balanced graphs

Mostrar todas las versiones(2)

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...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Bonomo, Flavia, Durán, Guillermo A., Safe, Martín Darío
Publicado: 2009
Materias:
balanced graphs
line graphs
P4-tidy graphs
paw-free graphs
perfect
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v35_nC_p41_Bonomo
http://hdl.handle.net/20.500.12110/paper_15710653_v35_nC_p41_Bonomo
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_15710653_v35_nC_p41_Bonomo
record_format dspace
spelling paper:paper_15710653_v35_nC_p41_Bonomo2023-06-08T16:24:26Z On minimal forbidden subgraph characterizations of balanced graphs Bonomo, Flavia Durán, Guillermo A. Safe, Martín Darío balanced graphs line graphs P4-tidy graphs paw-free graphs perfect 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. Fil:Bonomo, F. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Durán, G. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Safe, M.D. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2009 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v35_nC_p41_Bonomo http://hdl.handle.net/20.500.12110/paper_15710653_v35_nC_p41_Bonomo
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic balanced graphs
line graphs
P4-tidy graphs
paw-free graphs
perfect
spellingShingle balanced graphs
line graphs
P4-tidy graphs
paw-free graphs
perfect
Bonomo, Flavia
Durán, Guillermo A.
Safe, Martín Darío
On minimal forbidden subgraph characterizations of balanced graphs
topic_facet balanced graphs
line graphs
P4-tidy graphs
paw-free graphs
perfect
description 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.
author Bonomo, Flavia
Durán, Guillermo A.
Safe, Martín Darío
author_facet Bonomo, Flavia
Durán, Guillermo A.
Safe, Martín Darío
author_sort Bonomo, Flavia
title On minimal forbidden subgraph characterizations of balanced graphs
title_short On minimal forbidden subgraph characterizations of balanced graphs
title_full On minimal forbidden subgraph characterizations of balanced graphs
title_fullStr On minimal forbidden subgraph characterizations of balanced graphs
title_full_unstemmed On minimal forbidden subgraph characterizations of balanced graphs
title_sort on minimal forbidden subgraph characterizations of balanced graphs
publishDate 2009
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v35_nC_p41_Bonomo
http://hdl.handle.net/20.500.12110/paper_15710653_v35_nC_p41_Bonomo
work_keys_str_mv AT bonomoflavia onminimalforbiddensubgraphcharacterizationsofbalancedgraphs
AT duranguillermoa onminimalforbiddensubgraphcharacterizationsofbalancedgraphs
AT safemartindario onminimalforbiddensubgraphcharacterizationsofbalancedgraphs
_version_ 1768546177747255296

Ejemplares similares