untitled
<OAI-PMH schemaLocation=http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd>
<responseDate>2018-01-17T12:08:01Z</responseDate>
<request identifier=oai:HAL:hal-01540756v1 verb=GetRecord metadataPrefix=oai_dc>http://api.archives-ouvertes.fr/oai/hal/</request>
<GetRecord>
<record>
<header>
<identifier>oai:HAL:hal-01540756v1</identifier>
<datestamp>2018-01-12</datestamp>
<setSpec>type:ART</setSpec>
<setSpec>subject:info</setSpec>
<setSpec>collection:CNRS</setSpec>
<setSpec>collection:UNIV-AG</setSpec>
<setSpec>collection:UNICE</setSpec>
<setSpec>collection:UNIV-PSUD</setSpec>
<setSpec>collection:INRIASO</setSpec>
<setSpec>collection:BNRMI</setSpec>
<setSpec>collection:UMR8623</setSpec>
<setSpec>collection:INRIA</setSpec>
<setSpec>collection:INRIA_TEST</setSpec>
<setSpec>collection:INRIA2</setSpec>
<setSpec>collection:INRIA-SOPHIA</setSpec>
<setSpec>collection:I3S</setSpec>
<setSpec>collection:CENTRALESUPELEC</setSpec>
<setSpec>collection:UNIV-PSUD-SACLAY</setSpec>
<setSpec>collection:CENTRALESUPELEC-SACLAY</setSpec>
<setSpec>collection:UCA-TEST</setSpec>
<setSpec>collection:INRIA2017</setSpec>
<setSpec>collection:UNIV-PARIS-SACLAY</setSpec>
<setSpec>collection:LRI-GALAC</setSpec>
<setSpec>collection:UNIV-COTEDAZUR</setSpec>
</header>
<metadata><dc>
<publisher>HAL CCSD</publisher>
<title lang=en>Applying clique-decomposition for computing Gromov hyperbolicity</title>
<creator>Cohen, Nathann</creator>
<creator>Coudert, David</creator>
<creator>Ducoffe, Guillaume</creator>
<creator>Lancin, Aurélien</creator>
<contributor>Graphes, Algorithmes et Combinatoire (LRI) (GALaC - LRI) ; Laboratoire de Recherche en Informatique (LRI) ; Université Paris-Sud - Paris 11 (UP11) - Institut National de Recherche en Informatique et en Automatique (Inria) - CentraleSupélec - Centre National de la Recherche Scientifique (CNRS) - Université Paris-Sud - Paris 11 (UP11) - Institut National de Recherche en Informatique et en Automatique (Inria) - CentraleSupélec - Centre National de la Recherche Scientifique (CNRS)</contributor>
<contributor>Combinatorics, Optimization and Algorithms for Telecommunications (COATI) ; Inria Sophia Antipolis - Méditerranée (CRISAM) ; Institut National de Recherche en Informatique et en Automatique (Inria) - Institut National de Recherche en Informatique et en Automatique (Inria) - COMmunications, Réseaux, systèmes Embarqués et Distribués (COMRED) ; Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S) ; Université Nice Sophia Antipolis (UNS) ; Université Côte d'Azur (UCA) - Université Côte d'Azur (UCA) - Centre National de la Recherche Scientifique (CNRS) - Université Nice Sophia Antipolis (UNS) ; Université Côte d'Azur (UCA) - Université Côte d'Azur (UCA) - Centre National de la Recherche Scientifique (CNRS) - Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S) ; Université Nice Sophia Antipolis (UNS) ; Université Côte d'Azur (UCA) - Université Côte d'Azur (UCA) - Centre National de la Recherche Scientifique (CNRS) - Université Nice Sophia Antipolis (UNS) ; Université Côte d'Azur (UCA) - Université Côte d'Azur (UCA) - Centre National de la Recherche Scientifique (CNRS)</contributor>
<contributor>Laboratoire de Mathématiques Informatique et Applications (LAMIA) ; Université des Antilles et de la Guyane (UAG)</contributor>
<description>International audience</description>
<source>ISSN: 0304-3975</source>
<source>Theoretical Computer Science</source>
<publisher>Elsevier</publisher>
<identifier>hal-01540756</identifier>
<identifier>https://hal.inria.fr/hal-01540756</identifier>
<identifier>https://hal.inria.fr/hal-01540756/document</identifier>
<identifier>https://hal.inria.fr/hal-01540756/file/CCDL-2017.pdf</identifier>
<source>https://hal.inria.fr/hal-01540756</source>
<source>Theoretical Computer Science, Elsevier, 2017, 690, pp.114-139. 〈10.1016/j.tcs.2017.06.001〉</source>
<identifier>DOI : 10.1016/j.tcs.2017.06.001</identifier>
<relation>info:eu-repo/semantics/altIdentifier/doi/10.1016/j.tcs.2017.06.001</relation>
<language>en</language>
<subject lang=en>clique-decomposition</subject>
<subject lang=en>graph algorithms</subject>
<subject lang=en>outerplanar graphs</subject>
<subject lang=en>Gromov hyperbolicity</subject>
<subject>[INFO.INFO-NI] Computer Science [cs]/Networking and Internet Architecture [cs.NI]</subject>
<type>info:eu-repo/semantics/article</type>
<type>Journal articles</type>
<description lang=en>Given a graph, its hyperbolicity is a measure of how close its distance distribution is to the one of a tree. This parameter has gained recent attention in the analysis of some graph algorithms and the classification of complex networks. We study on practical improvements for the computation of hyperbolicity in large graphs. Precisely, we investigate on relations between the hyperbolicity of a graph G and the hyperbolicity of its atoms, that are the subgraphs output by the clique-decomposition invented by Tarjan [51, 65]. We prove that the maximum hyperbolicity taken over the atoms is at most one unit off from the hyperbol-icity of G and the bound is sharp. We also give an algorithm to slightly modify the atoms, called the " substitution method " , which is at no extra cost than computing the clique-decomposition, and so that the maximum hyperbolicity taken over the resulting graphs is exactly the hyperbolicity of the input graph G. An experimental evaluation of our method for computing the hyperbolicity of a given graph from its atoms is provided for collaboration networks and biological networks. Finally, on a more theoretical side, we deduce from our results the first linear-time algorithm for computing the hyperbolicity of an outerplanar graph.</description>
<date>2017</date>
<contributor>ANR-13-BS02-0007, Stint, Structures Interdites(2013)</contributor>
<contributor>ANR-11-LABX-0031-01, UCN@Sophia, Labex User Centric Network Sophia Antipolis</contributor>
</dc>
</metadata>
</record>
</GetRecord>
</OAI-PMH>
