BACK TO COATI PUBLICATION INDEX
Publications of year 2016
-
Fedor V. Fomin,
Pierre Fraigniaud,
Nicolas Nisse,
and Dimitrios M. Thilikos.
Forewords: Special issue on Theory and Applications of Graph Searching Problems,
volume 655:1 of Theoretical Computer Science - Special Issue on Theory and Applications of Graph Searching Problems.
December 2016.
[WWW
] [bibtex-entry]
-
Guillaume Ducoffe.
Metric properties of large graphs.
Theses,
Université Côte d'Azur,
December 2016.
[WWW
] [PDF
]
Keywords:
Graph,
Algorithms,
Complexity in P,
Gromov Hyperbolicity,
Treelength,
Treebreadth,
Treewidth,
Coloring games,
Nash equilibrium,
Boolean function learning,
Algorithmes,
Complexité dans P,
Hyperbolicité,
Jeux de coloration,
Équilibre de Nash,
Apprentissage de fonction booléenne,
Graphe.
[bibtex-entry]
-
J Araujo,
Frédéric Giroire,
J Moulierac,
Yi Liu,
and R Modrzejewski.
Energy Efficient Content Distribution.
The Computer Journal,
59(2):192-207,
February 2016.
[WWW
] [PDF
]
Keywords:
Energy Efficiency,
Integer Linear Programming,
Content Deliv-ery Network,
In-network Caching,
Future Internet.
[bibtex-entry]
-
Julio Araujo,
Frédéric Havet,
Claudia Linhares Sales,
and Ana Silva.
Proper orientation of cacti.
Journal of Theoretical Computer Science (TCS),
639:14-25,
2016.
[WWW
] [PDF
]
Keywords:
proper orientation,
graph coloring,
cactus graph,
claw-free graph,
planar graph,
block graph.
[bibtex-entry]
-
Julio Araujo,
Gregory Morel,
Leonardo Sampaio,
Ronan Soares,
and Valentin Weber.
Hull number: P5-free graphs and reduction rules.
Discrete Applied Mathematics,
210:171 - 175,
September 2016.
[WWW
] [bibtex-entry]
-
Joergen Bang-Jensen,
Nathann Cohen,
and Frédéric Havet.
Finding good 2-partitions of digraphs II. Enumerable properties.
Journal of Theoretical Computer Science (TCS),
640:1-19,
August 2016.
[WWW
] [PDF
]
Keywords:
Feedback vertex set,
Out-branching,
Tournament,
Oriented,
NP-complete,
Polynomial,
Partition,
Splitting digraphs,
Acyclic,
Semicomplete digraph,
2-Partition,
Minimum degree.
[bibtex-entry]
-
J Bang-Jensen and Frédéric Havet.
Finding good 2-partitions of digraphs I. Hereditary properties.
Journal of Theoretical Computer Science (TCS),
636:85--94,
2016.
[WWW
] [PDF
]
Keywords:
minimum degree,
2-partition,
tournament,
out-branching,
feedback vertex set,
oriented,
NP-complete,
polynomial,
partition,
splitting digraphs,
acyclic,
semicomplete digraph.
[bibtex-entry]
-
J Bang-Jensen,
Frédéric Havet,
and Anders Yeo.
The complexity of finding arc-disjoint branching flows.
Discrete Applied Mathematics,
209:16-26,
2016.
[WWW
] [PDF
] [bibtex-entry]
-
Jean-Claude Bermond,
Cristiana Gomes Huiban,
and Patricio Reyes.
Round weighting problem and gathering in radio networks with symmetrical interference.
Discrete Mathematics, Algorithms and Applications,
8(2):1650035 57 pages,
2016.
[WWW
]
Keywords:
Radio networks,
wireless networks,
interference,
grids,
gathering,
bounds,
approximation algorithms..
[bibtex-entry]
-
Jean-Claude Bermond,
Alain Jean-Marie,
Dorian Mazauric,
and Joseph Yu.
Well Balanced Designs for Data Placement.
Journal of Combinatorial Designs,
24(2):55-76,
February 2016.
[WWW
] [PDF
] [bibtex-entry]
-
David Coudert,
Guillaume Ducoffe,
and Nicolas Nisse.
To Approximate Treewidth, Use Treelength!.
Siam Journal on Discrete Mathematics,
30(3):13,
2016.
[WWW
] [PDF
]
Keywords:
Graph,
Treewidth,
Treelength,
Cycle basis,
Genus.
[bibtex-entry]
-
David Coudert and Guillaume Ducoffe.
Data center interconnection networks are not hyperbolic.
Theoretical Computer Science,
639:72-90,
2016.
[WWW
] [PDF
]
Keywords:
interconnection network,
data center,
Cayley graph,
greedy routing scheme,
metric embedding,
graph endomorphism,
Gromov hy-perbolicity.
[bibtex-entry]
-
David Coudert and Guillaume Ducoffe.
On the hyperbolicity of bipartite graphs and intersection graphs.
Discrete Applied Mathematics,
214:187-195,
2016.
[WWW
] [PDF
]
Keywords:
biclique graph,
line graph,
clique graph,
Gromov hyperbolicity,
bipartite graph,
intersection graph,
graph power.
[bibtex-entry]
-
David Coudert,
Dorian Mazauric,
and Nicolas Nisse.
Experimental Evaluation of a Branch and Bound Algorithm for Computing Pathwidth and Directed Pathwidth.
ACM Journal of Experimental Algorithmics,
21(1):23,
2016.
[WWW
] [PDF
] [bibtex-entry]
-
David Coudert,
Stéphane Pérennes,
Hervé Rivano,
and Marie-Emilie Voge.
Combinatorial optimization in networks with Shared Risk Link Groups.
Discrete Mathematics and Theoretical Computer Science,
Vol. 18, no 3:25,
May 2016.
[WWW
] [PDF
]
Keywords:
colored graphs,
Shared Risk Link Group,
complexity,
algorithms,
Multi-layer networks.
[bibtex-entry]
-
Nicolas Nisse and Ronan Pardo Soares.
On the Monotonicity of Process Number.
Discrete Applied Mathematics,
210:103-111,
2016.
[WWW
] [PDF
]
Keywords:
Graph Searching,
Process Number,
Monotonicity.
[bibtex-entry]
-
Jean-Claude Bermond,
Nathann Cohen,
David Coudert,
Dimitrios Letsios,
Ioannis Milis,
Stéphane Pérennes,
and Vassilis Zissimopoulos.
Bin Packing with Colocations.
In Klaus Jansen and Monaldo Mastrolilli, editors,
14th International Workshop on Approximation and Online Algorithms (WAOA),
volume 10138,
Aarhus, Denmark,
pages 40-51,
August 2016.
Springer.
[WWW
] [PDF
] [bibtex-entry]
-
Marwane Bouznif,
Frédéric Havet,
and Myriam Preissmann.
Minimum-Density Identifying Codes in Square Grids.
In 11th International Conference, AAIM 2016,
volume 9778 of Lecture Notes in Computer Science,
Bergamo, Italy,
pages 77-88,
July 2016.
Riccardo Dondi,
Springer.
[WWW
] [PDF
]
Keywords:
identifying code,
square grid,
discharging method.
[bibtex-entry]
-
Nathann Cohen,
Frédéric Havet,
William Lochet,
and Nicolas Nisse.
Subdivisions of oriented cycles in digraphs with large chromatic number.
In Bordeaux Graph Wokshop 2016,
Bordeaux, France,
pages 85-88,
November 2016.
[WWW
] [PDF
] [bibtex-entry]
-
Nathann Cohen,
Mathieu Hilaire,
Nicolas Martins,
Nicolas Nisse,
and Stéphane Pérennes.
Spy-Game on graphs.
In Erik D. Demaine and Fabrizio Grandoni, editors,
8th International Conference on Fun with Algorithms, FUN 2016,
volume 49 of Leibniz International Proceedings in Informatics (LIPIcs),
La Maddalena, Maddalena Islands, Italy,
2016.
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik.
[WWW
] [PDF
] [bibtex-entry]
-
David Coudert and Guillaume Ducoffe.
Liens entre symétries et étirements de routages dans les réseaux d'interconnexions de centres de données.
In ALGOTEL 2016 - 18èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications,
Bayonne, France,
May 2016.
[WWW
] [PDF
]
Keywords:
Mots-clefs : Graphe,
Centre de données,
Routage géométrique,
Endomorphisme de graphe,
Hyperbolicité.
[bibtex-entry]
-
Rennan Dantas,
Frédéric Havet,
and Rudini M Sampaio.
Identifying codes for infinite triangular grids with a finite number of rows.
In Bordeaux Graph Workshop 2016,
Bordeaux, France,
November 2016.
[WWW
] [PDF
] [bibtex-entry]
-
Guillaume Ducoffe.
The Parallel Complexity of Coloring Games.
In Martin Gairing and Rahul Savani, editors,
9th International Symposium, SAGT 2016,
number 9928 of Algorithmic Game Theory,
Liverpool, United Kingdom,
pages 27-39,
September 2016.
Springer International Publishing.
[WWW
] [PDF
] [bibtex-entry]
-
Guillaume Ducoffe,
Sylvain Legay,
and Nicolas Nisse.
On the Complexity of Computing Treebreadth.
In Veli Mäkinen,
Simon J. Puglisi,
and Leena Salmela, editors,
27th International Workshop on Combinatorial Algorithms, IWOCA 2016,
number 9843 of Combinatorial Algorithms,
Helsinki, Finland,
pages 3-15,
August 2016.
Springer International Publishing.
[WWW
] [PDF
] [bibtex-entry]
-
Frédéric Giroire and Nicolas Huin.
Étude d'un système distribué de diffusion de vidéo en direct.
In ALGOTEL 2016 - 18èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications,
Bayonne, France,
May 2016.
[WWW
] [PDF
]
Keywords:
pair-à-pair.
[bibtex-entry]
-
Myriana Rifai,
Nicolas Huin,
Christelle Caillouet,
Frédéric Giroire,
Joanna Moulierac,
Dino Lopez Pacheco,
and Guillaume Urvoy-Keller.
MINNIE : enfin un monde SDN sans (trop de) règles.
In ALGOTEL 2016 - 18èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications,
Bayonne, France,
May 2016.
[WWW
] [PDF
] [bibtex-entry]
-
Julio Araujo,
Guillaume Ducoffe,
Nicolas Nisse,
and Karol Suchan.
On interval number in cycle convexity.
Research Report,
Inria Sophia Antipolis ; I3S,
2016.
[WWW
] [PDF
]
Keywords:
graph,
convexity,
complexity,
dominating set.
[bibtex-entry]
-
Julio Araujo,
Frédéric Giroire,
Yaning Y.L. Liu,
Remigiusz Modrzejewski,
and Joanna Moulierac.
Energy Efficient Content Distribution.
Research Report RR-8091,
INRIA,
January 2016.
[WWW
] [PDF
]
Keywords:
Energy Efficiency,
Integer Linear Programming,
Content Delivery Network,
Net- work Cache,
Future Internet.
[bibtex-entry]
-
Jorgen Bang-Jensen,
Nathann Cohen,
and Frédéric Havet.
Finding good 2-partitions of digraphs II. Enumerable properties.
Research Report RR-8868,
INRIA Sophia Antipolis - I3S,
February 2016.
[WWW
] [PDF
] [bibtex-entry]
-
Jorgen Bang-Jensen and Frédéric Havet.
Finding good 2-partitions of digraphs I. Hereditary properties.
Research Report RR-8867,
INRIA Sophia Antipolis - I3S,
February 2016.
[WWW
] [PDF
] [bibtex-entry]
-
Olivier Baudon,
Julien Bensmail,
Hervé Hocquard,
Mohammed Senhaji,
and Eric Sopena.
On locally irregular decompositions of subcubic graphs.
Research Report,
Université de bordeaux ; Université de Nice - Sophia Antipolis,
2016.
[WWW
] [PDF
] [bibtex-entry]
-
Olivier Baudon,
Julien Bensmail,
Jakub Przybylo,
and Mariusz Wozniak.
On locally irregular decompositions and the 1-2 Conjecture in digraphs.
Research Report,
Inria, CNRS, Université de Bordeaux, AGH University,
September 2016.
[WWW
] [PDF
] [bibtex-entry]
-
Jean-Claude Bermond,
Nathann Cohen,
David Coudert,
Dimitrios Letsios,
Ioannis Milis,
Stéphane Pérennes,
and Vassilis Zissimopoulos.
Bin packing with colocations.
Research Report,
Inria ; I3S,
October 2016.
[WWW
] [PDF
] [bibtex-entry]
-
Marwane Bouznif,
Frédéric Havet,
and Myriam Preissmann.
Minimum-density identifying codes in square grids.
Research Report RR-8845,
INRIA Sophia Antipolis - I3S,
January 2016.
[WWW
] [PDF
] [bibtex-entry]
-
Nathann Cohen,
Frédéric Havet,
William Lochet,
and Nicolas Nisse.
Subdivisions of oriented cycles in digraphs with large chromatic number.
Research Report RR-8865,
LRI - CNRS, University Paris-Sud ; LIP - ENS Lyon ; INRIA Sophia Antipolis - I3S,
February 2016.
[WWW
] [PDF
] [bibtex-entry]
-
Nathann Cohen,
Mathieu Hilaire,
Nicolas Martins,
Nicolas Nisse,
and Stéphane Pérennes.
Spy-Game on graphs.
Research Report RR-8869,
Inria,
February 2016.
[WWW
] [PDF
] [bibtex-entry]
-
David Coudert and Guillaume Ducoffe.
Clique-decomposition revisited.
Research Report,
INRIA Sophia Antipolis - I3S,
February 2016.
[WWW
] [PDF
]
Keywords:
planar graphs,
treewidth,
clique-decomposition,
minimal triangulation,
clique-number,
bounded-degree graphs.
[bibtex-entry]
-
David Coudert.
A note on Integer Linear Programming formulations for linear ordering problems on graphs.
Research Report,
Inria ; I3S ; Universite Nice Sophia Antipolis ; CNRS,
February 2016.
[WWW
] [PDF
] [bibtex-entry]
-
David Coudert,
Guillaume Ducoffe,
Nicolas Nisse,
and Mauricio Soto.
Distance-preserving orderings in graphs.
Research Report RR-8973,
Inria Sophia Antipolis,
2016.
[WWW
] [PDF
]
Keywords:
bounded treewidth,
distance-preserving elimination ordering,
metric graph theory,
NP-complete,
exact expo- nential algorithm,
integer linear programming.
[bibtex-entry]
-
David Coudert,
James Luedtke,
Eduardo Moreno,
and Konstantinos Priftis.
Computing and maximizing the exact reliability of wireless backhaul networks.
Research Report,
Inria Sophia Antipolis ; I3S,
November 2016.
[WWW
] [PDF
]
Keywords:
Network design,
Backhaul network,
Reliability,
Optimization.
[bibtex-entry]
-
Rennan Dantas,
Frédéric Havet,
and Rudini Sampaio.
Identifying codes for infinite triangular grids with a finite number of rows.
Research Report RR-8951,
INRIA Sophia Antipolis - I3S,
August 2016.
[WWW
] [PDF
]
Keywords:
identifying code,
grid,
discharging method,
méthode de déchargement,
grille,
code identifiant.
[bibtex-entry]
-
Guillaume Ducoffe,
Sylvain Legay,
and Nicolas Nisse.
On computing tree and path decompositions with metric constraints on the bags.
Research Report RR-8842,
INRIA Sophia Antipolis - Méditerranée ; LRI - CNRS, University Paris-Sud,
January 2016.
[WWW
] [PDF
]
Keywords:
path-breadth,
k-good tree decompositions,
tree-length,
tree-breadth,
path-length.
[bibtex-entry]
-
Frédéric Giroire,
Nicolas Huin,
Joanna Moulierac,
and Khoa Phan.
Energy-Aware Routing in Software-Defined Networks with Table Compression (using Wildcard Rules).
Research Report RR-8897,
INRIA Sophia Antipolis - I3S,
April 2016.
[WWW
] [PDF
]
Keywords:
energy savings,
backbone networks,
Software Defined Networks,
data center networks,
routing tables,
compression,
TCAM memory,
réseaux programmables,
réseaux de centre de données,
table de routage,
mémoire TCAM,
économie d'énergie,
réseau backbone.
[bibtex-entry]
-
Frédéric Giroire and Juan-Carlos Maureira.
Analysis of the Failure Tolerance of Linear Access Networks.
Research Report RR-8903,
CNRS, University of Nice Sophia Antipolis, I3S, UMR 7271, COATI, Inria, 06900 Sophia Antipolis, France ; Center of Mathematical Modeling, University of Chile, Chile ; Inria Sophia Antipolis,
April 2016.
[WWW
] [PDF
]
Keywords:
Access networks,
failure tolerance,
telecommuting,
connectivity analysis,
maintenance cost.
[bibtex-entry]
-
Nicolas Huin,
Andrea Tomassilli,
Frédéric Giroire,
and Brigitte Jaumard.
Energy-Efficient Service Function Chain Provisioning.
Research Report RR-8980,
Inria Sophia Antipolis ; Université Côte d'Azur ; Cnrs ; Concordia University,
November 2016.
[WWW
] [PDF
]
Keywords:
Column Generation,
Network Function Virtualization,
Service Function Chains,
Software Defined Networks,
Energy Efficiency,
Optimization,
Optimisation,
Efficacité énergétique,
Réseaux logiciels,
Virtualisation des fonctions réseaux,
Chaînes de fonctions de service,
Génération de Colonnes.
[bibtex-entry]
-
Myriana Rifai,
Nicolas Huin,
Christelle Caillouet,
Frédéric Giroire,
Joanna Moulierac,
Dino Lopez Pacheco,
and Guillaume Urvoy-Keller.
MINNIE: an SDN World with Few Compressed Forwarding Rules.
Research Report RR-8848,
INRIA Sophia-Antipolis ; I3S,
January 2016.
[WWW
] [PDF
]
Keywords:
Software Defined Networks,
data center networks,
routing tables,
compression,
TCAM memory.
[bibtex-entry]
-
Andrea Tomassilli,
Nicolas Huin,
Frédéric Giroire,
and Brigitte Jaumard.
Energy-Efficient Service Chains with Network Function Virtualization.
Research Report RR-8979,
Inria Sophia Antipolis ; Université Côte d'Azur ; Cnrs ; Concordia University,
October 2016.
[WWW
] [PDF
]
Keywords:
Optimization,
Energy Efficiency,
Network Function Virtualization,
Service Function Chains,
Software Defined Networks,
Chaînes de fonctions de service,
Virtualisation des fonctions réseaux,
Réseaux logiciels,
Efficacité énergétique,
Optimisation.
[bibtex-entry]
-
Luc Hogie,
Michel Syska,
and Nicolas Chleq.
BigGraphs: distributed graph computing,
September 2016.
[WWW
] [bibtex-entry]
-
Pierre Aboulker,
Jorgen Bang-Jensen,
Nicolas Bousquet,
Pierre Charbit,
Frédéric Havet,
Frédéric Maffray,
and Jose Zamora.
$\chi$-bounded families of oriented graphs.
Note: Working paper or preprint,
2016.
[WWW
] [PDF
] [bibtex-entry]
-
Seong-Gyun Jeong,
Yuliya Tarabalka,
Nicolas Nisse,
and Josiane Zerubia.
Progressive Tree-like Curvilinear Structure Reconstruction with Structured Ranking Learning and Graph Algorithm.
Note: Working paper or preprint,
December 2016.
[WWW
] [PDF
] [bibtex-entry]
BACK TO COATI PUBLICATION INDEX
Last modified: Sat Jan 29 19:00:41 2022
