Metric properties of large graphs
Identifieur interne : 000020 ( Main/Exploration ); précédent : 000019; suivant : 000021Metric properties of large graphs
Auteurs : Guillaume Ducoffe [France]Source :
Descripteurs français
- mix :
English descriptors
- mix :
Abstract
Large scale communication networks are everywhere, ranging from data centers withmillions of servers to social networks with billions of users. This thesis is devoted tothe fine-grained complexity analysis of combinatorial problems on these networks.In the first part, we focus on the embeddability of communication networks totree topologies. This property has been shown to be crucial in the understandingof some aspects of network traffic (such as congestion). More precisely, we studythe computational complexity of Gromov hyperbolicity and of tree decompositionparameters in graphs – including treelength and treebreadth. On the way, we givenew bounds on these parameters in several graph classes of interest, some of thembeing used in the design of data center interconnection networks. The main resultin this part is a relationship between treelength and treewidth: another well-studiedgraph parameter, that gives a unifying view of treelikeness in graphs and has algorithmicapplications. This part borrows from graph theory and recent techniques incomplexity theory. The second part of the thesis is on the modeling of two privacy concerns with social networking services. We aim at analysing information flows in these networks,represented as dynamical processes on graphs. First, a coloring game on graphs isstudied as a solution concept for the dynamic of online communities. We give afine-grained complexity analysis for computing Nash and strong Nash equilibria inthis game, thereby answering open questions from the literature. On the way, wepropose new directions in algorithmic game theory and parallel complexity, usingcoloring games as a case example
Url:
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Hal, to step Corpus: 000095
- to stream Hal, to step Curation: 000095
- to stream Hal, to step Checkpoint: 000019
- to stream Main, to step Merge: 000020
- to stream Main, to step Curation: 000020
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Metric properties of large graphs</title>
<title xml:lang="fr">Propriétés métriques des grands graphes</title>
<author><name sortKey="Ducoffe, Guillaume" sort="Ducoffe, Guillaume" uniqKey="Ducoffe G" first="Guillaume" last="Ducoffe">Guillaume Ducoffe</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-211142" status="VALID"><idno type="RNSR">201322124W</idno>
<orgName>Combinatorics, Optimization and Algorithms for Telecommunications</orgName>
<orgName type="acronym">COATI</orgName>
<desc><address><addrLine>2004 route des Lucioles BP 93 F-06902 Sophia Antipolis (France)</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/equipes/coati</ref>
</desc>
<listRelation><relation active="#struct-34586" type="direct"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-451999" type="direct"></relation>
<relation active="#struct-13009" type="indirect"></relation>
<relation active="#struct-117617" type="indirect"></relation>
<relation active="#struct-523042" type="indirect"></relation>
<relation name="UMR7271" active="#struct-441569" type="indirect"></relation>
</listRelation>
<tutelles><tutelle active="#struct-34586" type="direct"><org type="laboratory" xml:id="struct-34586" status="VALID"> <idno type="RNSR">198318250R</idno>
<orgName>Inria Sophia Antipolis - Méditerranée </orgName>
<orgName type="acronym">CRISAM</orgName>
<desc> <address> <addrLine>2004 route des Lucioles BP 93 06902 Sophia Antipolis</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/centre/sophia/</ref>
</desc>
<listRelation> <relation active="#struct-300009" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"> <orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc> <address> <addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-451999" type="direct"><org type="department" xml:id="struct-451999" status="VALID"><orgName>COMmunications, Réseaux, systèmes Embarqués et Distribués</orgName>
<orgName type="acronym">COMRED</orgName>
<date type="start">2016-03-02</date>
<desc><address><addrLine>Laboratoire I3SCS 4012106903 Sophia Antipolis Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.i3s.unice.fr/comred</ref>
</desc>
<listRelation><relation active="#struct-13009" type="direct"></relation>
<relation active="#struct-117617" type="indirect"></relation>
<relation active="#struct-523042" type="indirect"></relation>
<relation name="UMR7271" active="#struct-441569" type="indirect"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-13009" type="indirect"><org type="laboratory" xml:id="struct-13009" status="VALID"><orgName>Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis</orgName>
<orgName type="acronym">I3S</orgName>
<desc><address><addrLine>2000, route des Lucioles - Les Algorithmes - bât. Euclide B 06900 Sophia Antipolis</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.i3s.unice.fr/</ref>
</desc>
<listRelation><relation active="#struct-117617" type="direct"></relation>
<relation active="#struct-523042" type="indirect"></relation>
<relation name="UMR7271" active="#struct-441569" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-117617" type="indirect"><org type="institution" xml:id="struct-117617" status="VALID"> <orgName>Université Nice Sophia Antipolis</orgName>
<orgName type="acronym">UNS</orgName>
<desc> <address> <addrLine>Parc Valrose - BP 2135 - 06103 Nice cedex 2</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://unice.fr/</ref>
</desc>
<listRelation> <relation active="#struct-523042" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-523042" type="indirect"><org type="regroupinstitution" xml:id="struct-523042" status="VALID"> <orgName>Université Côte d'Azur </orgName>
<orgName type="acronym">UCA</orgName>
<date type="start">2015-03-01</date>
<desc> <address> <addrLine>Parc Valrose, 28 avenue Valrose 06108 Nice Cedex 2 </addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle name="UMR7271" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"> <idno type="IdRef">02636817X</idno>
<idno type="ISNI">0000000122597504</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc> <address> <country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Nice</settlement>
<region type="region" nuts="2">Provence-Alpes-Côte d'Azur</region>
</placeName>
<orgName type="university">Université Nice Sophia Antipolis</orgName>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:tel-01485328</idno>
<idno type="halId">tel-01485328</idno>
<idno type="halUri">https://tel.archives-ouvertes.fr/tel-01485328</idno>
<idno type="url">https://tel.archives-ouvertes.fr/tel-01485328</idno>
<date when="2016-12-09">2016-12-09</date>
<idno type="wicri:Area/Hal/Corpus">000095</idno>
<idno type="wicri:Area/Hal/Curation">000095</idno>
<idno type="wicri:Area/Hal/Checkpoint">000019</idno>
<idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">000019</idno>
<idno type="wicri:Area/Main/Merge">000020</idno>
<idno type="wicri:Area/Main/Curation">000020</idno>
<idno type="wicri:Area/Main/Exploration">000020</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">Metric properties of large graphs</title>
<title xml:lang="fr">Propriétés métriques des grands graphes</title>
<author><name sortKey="Ducoffe, Guillaume" sort="Ducoffe, Guillaume" uniqKey="Ducoffe G" first="Guillaume" last="Ducoffe">Guillaume Ducoffe</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-211142" status="VALID"><idno type="RNSR">201322124W</idno>
<orgName>Combinatorics, Optimization and Algorithms for Telecommunications</orgName>
<orgName type="acronym">COATI</orgName>
<desc><address><addrLine>2004 route des Lucioles BP 93 F-06902 Sophia Antipolis (France)</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/equipes/coati</ref>
</desc>
<listRelation><relation active="#struct-34586" type="direct"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-451999" type="direct"></relation>
<relation active="#struct-13009" type="indirect"></relation>
<relation active="#struct-117617" type="indirect"></relation>
<relation active="#struct-523042" type="indirect"></relation>
<relation name="UMR7271" active="#struct-441569" type="indirect"></relation>
</listRelation>
<tutelles><tutelle active="#struct-34586" type="direct"><org type="laboratory" xml:id="struct-34586" status="VALID"> <idno type="RNSR">198318250R</idno>
<orgName>Inria Sophia Antipolis - Méditerranée </orgName>
<orgName type="acronym">CRISAM</orgName>
<desc> <address> <addrLine>2004 route des Lucioles BP 93 06902 Sophia Antipolis</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/centre/sophia/</ref>
</desc>
<listRelation> <relation active="#struct-300009" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"> <orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc> <address> <addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-451999" type="direct"><org type="department" xml:id="struct-451999" status="VALID"><orgName>COMmunications, Réseaux, systèmes Embarqués et Distribués</orgName>
<orgName type="acronym">COMRED</orgName>
<date type="start">2016-03-02</date>
<desc><address><addrLine>Laboratoire I3SCS 4012106903 Sophia Antipolis Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.i3s.unice.fr/comred</ref>
</desc>
<listRelation><relation active="#struct-13009" type="direct"></relation>
<relation active="#struct-117617" type="indirect"></relation>
<relation active="#struct-523042" type="indirect"></relation>
<relation name="UMR7271" active="#struct-441569" type="indirect"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-13009" type="indirect"><org type="laboratory" xml:id="struct-13009" status="VALID"><orgName>Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis</orgName>
<orgName type="acronym">I3S</orgName>
<desc><address><addrLine>2000, route des Lucioles - Les Algorithmes - bât. Euclide B 06900 Sophia Antipolis</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.i3s.unice.fr/</ref>
</desc>
<listRelation><relation active="#struct-117617" type="direct"></relation>
<relation active="#struct-523042" type="indirect"></relation>
<relation name="UMR7271" active="#struct-441569" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-117617" type="indirect"><org type="institution" xml:id="struct-117617" status="VALID"> <orgName>Université Nice Sophia Antipolis</orgName>
<orgName type="acronym">UNS</orgName>
<desc> <address> <addrLine>Parc Valrose - BP 2135 - 06103 Nice cedex 2</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://unice.fr/</ref>
</desc>
<listRelation> <relation active="#struct-523042" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-523042" type="indirect"><org type="regroupinstitution" xml:id="struct-523042" status="VALID"> <orgName>Université Côte d'Azur </orgName>
<orgName type="acronym">UCA</orgName>
<date type="start">2015-03-01</date>
<desc> <address> <addrLine>Parc Valrose, 28 avenue Valrose 06108 Nice Cedex 2 </addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle name="UMR7271" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"> <idno type="IdRef">02636817X</idno>
<idno type="ISNI">0000000122597504</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc> <address> <country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Nice</settlement>
<region type="region" nuts="2">Provence-Alpes-Côte d'Azur</region>
</placeName>
<orgName type="university">Université Nice Sophia Antipolis</orgName>
</affiliation>
</author>
</analytic>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass><keywords scheme="mix" xml:lang="en"><term>Algorithms</term>
<term>Boolean function learning</term>
<term>Coloring games</term>
<term>Complexity in P</term>
<term>Graph</term>
<term>Gromov Hyperbolicity</term>
<term>Nash equilibrium</term>
<term>Treebreadth</term>
<term>Treelength</term>
<term>Treewidth</term>
</keywords>
<keywords scheme="mix" xml:lang="fr"><term>Algorithmes</term>
<term>Apprentissage de fonction booléenne</term>
<term>Complexité dans P</term>
<term>Graphe</term>
<term>Hyperbolicité</term>
<term>Jeux de coloration</term>
<term>Équilibre de Nash</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Large scale communication networks are everywhere, ranging from data centers withmillions of servers to social networks with billions of users. This thesis is devoted tothe fine-grained complexity analysis of combinatorial problems on these networks.In the first part, we focus on the embeddability of communication networks totree topologies. This property has been shown to be crucial in the understandingof some aspects of network traffic (such as congestion). More precisely, we studythe computational complexity of Gromov hyperbolicity and of tree decompositionparameters in graphs – including treelength and treebreadth. On the way, we givenew bounds on these parameters in several graph classes of interest, some of thembeing used in the design of data center interconnection networks. The main resultin this part is a relationship between treelength and treewidth: another well-studiedgraph parameter, that gives a unifying view of treelikeness in graphs and has algorithmicapplications. This part borrows from graph theory and recent techniques incomplexity theory. The second part of the thesis is on the modeling of two privacy concerns with social networking services. We aim at analysing information flows in these networks,represented as dynamical processes on graphs. First, a coloring game on graphs isstudied as a solution concept for the dynamic of online communities. We give afine-grained complexity analysis for computing Nash and strong Nash equilibria inthis game, thereby answering open questions from the literature. On the way, wepropose new directions in algorithmic game theory and parallel complexity, usingcoloring games as a case example</div>
</front>
</TEI>
<affiliations><list><country><li>France</li>
</country>
<region><li>Provence-Alpes-Côte d'Azur</li>
</region>
<settlement><li>Nice</li>
</settlement>
<orgName><li>Université Nice Sophia Antipolis</li>
</orgName>
</list>
<tree><country name="France"><region name="Provence-Alpes-Côte d'Azur"><name sortKey="Ducoffe, Guillaume" sort="Ducoffe, Guillaume" uniqKey="Ducoffe G" first="Guillaume" last="Ducoffe">Guillaume Ducoffe</name>
</region>
</country>
</tree>
</affiliations>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Psychologie/explor/BernheimV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000020 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000020 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Psychologie |area= BernheimV1 |flux= Main |étape= Exploration |type= RBID |clé= Hal:tel-01485328 |texte= Metric properties of large graphs }}
![]() | This area was generated with Dilib version V0.6.33. | ![]() |