Busque entre los 155933 recursos disponibles en el repositorio
Mostrar el registro sencillo del ítem
dc.date.accessioned | 2019-10-25T17:13:14Z | |
dc.date.available | 2019-10-25T17:13:14Z | |
dc.date.issued | 2012 | |
dc.identifier.uri | http://sedici.unlp.edu.ar/handle/10915/84095 | |
dc.description.abstract | Every chordal graph G admits a representation as the intersection graph of a family of subtrees of a tree. A classic way of finding such an intersection model is to look for a maximum spanning tree of the valuated clique graph of G. Similar techniques have been applied to find intersection models of chordal graph subclasses as interval graphs and path graphs. In this work, we extend those methods to be applied beyond chordal graphs: we prove that a graph G can be represented as the intersection of a Helly separating family of graphs belonging to a given class if and only if there exists a spanning subgraph of the clique graph of G satisfying a particular condition. Moreover, such a spanning subgraph is characterized by its weight in the valuated clique graph of G. The specific case of Helly circular-arc graphs is treated. We show that the canonical intersection models of those graphs correspond to the maximum spanning cycles of the valuated clique graph. | en |
dc.format.extent | 1148-1157 | es |
dc.language | en | es |
dc.subject | Chordal graphs | es |
dc.subject | Clique-tree | es |
dc.subject | Helly circular-arc graphs | es |
dc.subject | Intersection models | es |
dc.title | Finding intersection models: From chordal to Helly circular-arc graphs | en |
dc.type | Articulo | es |
sedici.identifier.other | doi:10.1016/j.disc.2011.11.036 | es |
sedici.identifier.other | eid:2-s2.0-84155176752 | es |
sedici.identifier.issn | 0012-365X | es |
sedici.creator.person | Alcón, Liliana Graciela | es |
sedici.creator.person | Gutiérrez, Marisa | es |
sedici.subject.materias | Matemática | es |
sedici.description.fulltext | true | es |
mods.originInfo.place | Facultad de Ciencias Exactas | es |
sedici.subtype | Articulo | es |
sedici.rights.license | Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) | |
sedici.rights.uri | http://creativecommons.org/licenses/by-nc-sa/4.0/ | |
sedici.description.peerReview | peer-review | es |
sedici.relation.journalTitle | Discrete Mathematics | es |
sedici.relation.journalVolumeAndIssue | vol. 312, no. 6 | es |
sedici.rights.sherpa | * Color: verde* Pre-print del autor: si* Post-print del autor: si* Versión de editor/PDF:no* Condiciones:>>Authors pre-print on any website, including arXiv and RePEC>>Author's post-print on author's personal website immediately>>Author's post-print on open access repository after an embargo period of between |