Mostrar el registro sencillo del ítem

dc.contributor.author
Bonomo, Flavia  
dc.contributor.author
Duran, Guillermo Alfredo  
dc.contributor.author
Safe, Martin Dario  
dc.contributor.author
Wagler, Annegret K.  
dc.date.available
2017-06-23T21:06:43Z  
dc.date.issued
2013-09  
dc.identifier.citation
Bonomo, Flavia; Duran, Guillermo Alfredo; Safe, Martin Dario; Wagler, Annegret K.; On minimal forbidden subgraph characterizations of balanced graphs; Elsevier Science; Discrete Applied Mathematics; 161; 13-14; 9-2013; 1925-1942  
dc.identifier.issn
0166-218X  
dc.identifier.uri
http://hdl.handle.net/11336/18827  
dc.description.abstract
A graph is balanced if its clique-matrix contains no edge–vertex incidence matrix of an odd chordless cycle as a submatrix. 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 graphs that belong to one of the following graph classes: complements of bipartite graphs, line graphs of multigraphs, and complements of line graphs of multigraphs. These characterizations lead to linear-time recognition algorithms for balanced graphs within the same three graph classes.  
dc.format
application/pdf  
dc.language.iso
eng  
dc.publisher
Elsevier Science  
dc.rights
info:eu-repo/semantics/openAccess  
dc.rights.uri
https://creativecommons.org/licenses/by-nc-nd/2.5/ar/  
dc.subject
Balanced Graphs  
dc.subject
Bipartite Graphs  
dc.subject
Hereditary Clique.Helly Graphs  
dc.subject
Line Graphs  
dc.subject
Perfect Graphs  
dc.subject.classification
Matemática Aplicada  
dc.subject.classification
Matemáticas  
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS  
dc.subject.classification
Ciencias de la Computación  
dc.subject.classification
Ciencias de la Computación e Información  
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS  
dc.title
On minimal forbidden subgraph characterizations of balanced graphs  
dc.type
info:eu-repo/semantics/article  
dc.type
info:ar-repo/semantics/artículo  
dc.type
info:eu-repo/semantics/publishedVersion  
dc.date.updated
2017-06-23T14:17:27Z  
dc.journal.volume
161  
dc.journal.number
13-14  
dc.journal.pagination
1925-1942  
dc.journal.pais
Países Bajos  
dc.journal.ciudad
Amsterdam  
dc.description.fil
Fil: Bonomo, Flavia. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina  
dc.description.fil
Fil: Duran, Guillermo Alfredo. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Cálculo; Argentina. Universidad de Chile; Chile. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina  
dc.description.fil
Fil: Safe, Martin Dario. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina  
dc.description.fil
Fil: Wagler, Annegret K.. Universite Blaise Pascal; Francia  
dc.journal.title
Discrete Applied Mathematics  
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.dam.2013.04.001  
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/http://www.sciencedirect.com/science/article/pii/S0166218X13001741  

Archivos asociados
Thumbnail
 
Tamaño: 624.3Kb
Formato: PDF
.