Author: "Frédéric Havet" / Topic: 010201 computation theory & mathematics - Searchworks@Jio Institute Digital Library Search Results

Your search keyword '"Frédéric Havet"' showing total 58 results

Start Over Author "Frédéric Havet" Topic 010201 computation theory & mathematics

58 results on '"Frédéric Havet"'

1. On the dichromatic number of surfaces

Author: Frédéric Havet, Clément Rambaud, Kolja Knauer, Pierre Aboulker, Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), 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 (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), ANR-16-CE40-0009,GATO,Graphes, Algorithmes et TOpologie(2016), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-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), and Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)
Subjects: dichromatic number, 010102 general mathematics, Torus, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Surface (topology), graphs on surfaces, 01 natural sciences, planar graphs, Planar graph, Combinatorics, symbols.namesake, 010201 computation theory & mathematics, Euler characteristic, symbols, Projective plane, 0101 mathematics, Klein bottle, Mathematics
Abstract: In this paper, we give bounds on the dichromatic number $\overrightarrow{\chi }(\varSigma )$ of a surface $\varSigma $, which is the maximum dichromatic number of an oriented graph embeddable on $\varSigma $. We determine the asymptotic behaviour of $\overrightarrow{\chi }(\varSigma )$ by showing that there exist constants $a_1$ and $a_2$ such that, $ a_1\frac{\sqrt{-c}}{\log (-c)} \le \overrightarrow{\chi }(\varSigma ) \le a_2 \frac{\sqrt{-c}}{\log (-c)} $ for every surface $\varSigma $ with Euler characteristic $c\le -2$. We then give more explicit bounds for some surfaces with high Euler characteristic. In particular, we show that the dichromatic numbers of the projective plane $\mathbb {N}_1$, the Klein bottle $\mathbb {N}_2$, the torus $\mathbb {S}_1$, and Dyck’s surface $\mathbb {N}_3$ are all equal to 3, and that the dichromatic numbers of the 5-torus $\mathbb {S}_5$ and the 10-cross surface $\mathbb {N}_{10}$ are equal to 4.
Published: 2021
Full Text: View/download PDF

2. On the semi-proper orientations of graphs

Author: Ali Dehghan, Frédéric Havet, Carleton University, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-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), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), 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 (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
Subjects: Applied Mathematics, 0211 other engineering and technologies, 021107 urban & regional planning, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Degeneracy (graph theory), Graph, Vertex (geometry), Planar graph, Combinatorics, symbols.namesake, 010201 computation theory & mathematics, Outerplanar graph, Bipartite graph, symbols, Discrete Mathematics and Combinatorics, Mathematics
Abstract: International audience; A weighted orientation of a graph G is a pair (D, w) where D is an orientation of G and w is an arc-weighting of D, that is an application A(D) → N \ {0}. The in-weight of a vertex v in a weighted orientation (D, w), denoted by S (D,w) (v), is the sum of the weights of arcs with head v in D. A semi-proper orientation is a weighted orientation such that two adjacent vertices have different in-weights. The semiproper orientation number of a graph G, denoted by − → χs(G), is min (D,w)∈Γ max v∈V (G) S (D,w) (v), where Γ is the set of all semi-proper orientations of G. A semi-proper orientation (D, w) of a graph G is optimal if max v∈V (G) S (D,w) (v) = − → χs(G). In this work, we show that every graph G has an optimal semi-proper orientation (D, w) such that the weight of each arc is 1 or 2. We then give some bounds on the semi-proper orientation number: we show Mad(G) 2 ≤ − → χs(G) ≤ Mad(G) 2 +χ(G)−1 and δ * (G)+1 2 ≤ − → χs(G) ≤ 2δ * (G) for all graph G, where Mad(G) and δ * (G) are the maximum average degree and the degeneracy of G, respectively. We then deduce that the maximum semi-proper orientation number of a tree is 2, of a cactus is 3, of an outerplanar graph is 4, and of a planar graph is 6. Finally, we consider the computational complexity of associated problems: we show that determining whether − → χs(G) = χ(G) is NP-complete for planar graphs G with − → χs(G) = 2; we also show that deciding whether − → χs(G) ≤ 2 is NP-complete for planar bipartite graphs G.
Published: 2021
Full Text: View/download PDF

3. A variant of the Erdős‐Sós conjecture

Author: Maya Stein, David R. Wood, Bruce Reed, Frédéric Havet, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-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), Center for Mathematical Modelling - Centro de Modelamiento Matematico [Santiago] (CMM), Universidad de Chile = University of Chile [Santiago] (UCHILE)-Centre National de la Recherche Scientifique (CNRS), Monash University [Melbourne], 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 (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
Subjects: Conjecture, Degree (graph theory), 010102 general mathematics, Graph theory, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Combinatorics, 010201 computation theory & mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology, 0101 mathematics, Mathematics
Abstract: International audience; A well-known conjecture of Erdős and Sós states that every graph with average degree exceeding $m−1$ contains every tree with m edges as a subgraph. We propose a variant of this conjecture, which states that every graph of maximum degree exceeding m and minimum degree at least $[\frac{2m}{3}]$ contains every tree with m edges. As evidence for our conjecture we show (i) for every m there is a g(m) such that the weakening of the conjecture obtained by replacing the first m by g(m) holds, and (ii) there is a $\gamma > 0$ such that the weakening of the conjecture obtained by replacing $[\frac{2m} {3}$ by $(1 − \gamma)m$ holds.
Published: 2020
Full Text: View/download PDF

4. Minimum density of identifying codes of king grids

Author: Rennan Dantas, Frédéric Havet, Rudini Menezes Sampaio, Parallelism, Graphs and Optimization Research Group (ParGO), Universidade Federal do Ceará = Federal University of Ceará (UFC), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-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), 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 (Laboratoire I3S - COMRED), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: Discrete mathematics, Applied Mathematics, Discharging method, Neighbourhood (graph theory), identifying codes, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Theoretical Computer Science, Combinatorics, king grids, Discharging Method, 010201 computation theory & mathematics, Identifying code, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, King grid, Minimum density, Mathematics
Abstract: A set C ⊆ V ( G ) is an identifying code in a graph G if for all v ∈ V ( G ) , C [ v ] ≠ ∅ , and for all distinct u , v ∈ V ( G ) , C [ u ] ≠ C [ v ] , where C [ v ] = N [ v ] ∩ C and N [ v ] denotes the closed neighbourhood of v in G. The minimum density of an identifying code in G is denoted by d ⁎ ( G ) . In this paper, we study the density of king grids which are strong product of two paths. We show that for every king grid G , d ⁎ ( G ) ≥ 2 / 9 . In addition, we show this bound is attained only for king grids which are strong products of two infinite paths. Given k ≥ 3 , we denote by K k the (infinite) king strip with k rows. We prove that d ⁎ ( K 3 ) = 1 / 3 , d ⁎ ( K 4 ) = 5 / 16 , d ⁎ ( K 5 ) = 4 / 15 and d ⁎ ( K 6 ) = 5 / 18 . We also prove that 2 9 + 8 81 k ≤ d ⁎ ( K k ) ≤ 2 9 + 4 9 k for every k ≥ 7 .
Published: 2017
Full Text: View/download PDF

5. Finding a subdivision of a prescribed digraph of order 4

Author: A. Karolinna Maia, Bojan Mohar, and Frédéric Havet
Subjects: Reduction (recursion theory), business.industry, 010102 general mathematics, Digraph, 0102 computer and information sciences, Mathematical proof, 01 natural sciences, Combinatorics, Algorithmic complexity, 010201 computation theory & mathematics, Discrete Mathematics and Combinatorics, Order (group theory), Point (geometry), Geometry and Topology, 0101 mathematics, business, Mathematics, Subdivision
Abstract: The problem of when a given digraph contains a subdivision of a fixed digraph F is considered. Bang-Jensen et al. [4] laid out foundations for approaching this problem from the algorithmic point of view. In this article, we give further support to several open conjectures and speculations about algorithmic complexity of finding F-subdivisions. In particular, up to five exceptions, we completely classify for which 4-vertex digraphs F, the F-subdivision problem is polynomial-time solvable and for which it is NP-complete. While all NP-hardness proofs are made by reduction from some version of the 2-linkage problem in digraphs, some of the polynomial-time solvable cases involve relatively complicated algorithms.
Published: 2017
Full Text: View/download PDF

6. Powers of paths in tournaments

Author: Alex Scott, Benny Sudakov, Jacob Fox, Frédéric Havet, Nemanja Draganić, Dániel Korándi, François Dross, António Girão, David Munhá Correia, William Lochet, Eidgenössische Technische Hochschule - Swiss Federal Institute of Technology [Zürich] (ETH Zürich), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Stanford University, Heidelberg University, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-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), University of Oxford [Oxford], University of Bergen (UiB), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), 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 (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), and University of Oxford
Subjects: Statistics and Probability, Applied Mathematics, 010102 general mathematics, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Square (algebra), Theoretical Computer Science, Power (physics), Combinatorics, Computational Theory and Mathematics, 010201 computation theory & mathematics, Path (graph theory), FOS: Mathematics, Mathematics - Combinatorics, Tournament, Combinatorics (math.CO), 0101 mathematics, Mathematics
Abstract: In this short note we prove that every tournament contains the $k$-th power of a directed path of linear length. This improves upon recent results of Yuster and of Gir\~ao. We also give a complete solution for this problem when $k=2$, showing that there is always a square of a directed path of length $\lceil 2n/3 \rceil-1$, which is best possible., Comment: 6 pages; updated affiliations; accepted at CPC
Published: 2020
Full Text: View/download PDF

7. On the Unavoidability of Oriented Trees

Author: François Dross, Frédéric Havet, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-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), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), Université Nice Sophia Antipolis (1965 - 2019) (UNS), 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 (Laboratoire I3S - COMRED), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: Arborescence, General Computer Science, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Theoretical Computer Science, Combinatorics, Unavoidable, Tree (descriptive set theory), oriented trees, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Order (group theory), Tournament, 0101 mathematics, ComputingMilieux_MISCELLANEOUS, Mathematics, Oriented tree, 010102 general mathematics, Ramsey theory, 020207 software engineering, Digraph, unavoidability, Computational Theory and Mathematics, 010201 computation theory & mathematics, Computer Science - Discrete Mathematics
Abstract: A digraph is n-unavoidable if it is contained in every tournament of order n. We first prove that every arborescence of order n with k leaves is ( n + k − 1 ) -unavoidable. We then prove that every oriented tree of order n ( n ≥ 2 ) with k leaves is ( 3 2 n + 3 2 k − 2 ) -unavoidable and ( 9 2 n − 5 2 k − 9 2 ) -unavoidable, and thus ( 21 8 n − 47 16 ) -unavoidable. Finally, we prove that every oriented tree of order n with k leaves is ( n + 144 k 2 − 280 k + 124 ) -unavoidable.
Published: 2019
Full Text: View/download PDF

8. Proper orientation of cacti

Author: Júlio Araújo, Cláudia Linhares Sales, Ana Silva, Frédéric Havet, Parallelism, Graphs and Optimization Research Group (ParGO), Universidade Federal do Ceará = Federal University of Ceará (UFC), 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 (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), FUNCAP/CNRS project GAIATO INC-0083- 00047.01.00/13, ANR-13-BS02-0007,Stint,Structures Interdites(2013), Université Nice Sophia Antipolis (... - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS)
Subjects: Factor-critical graph, General Computer Science, planar graph, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], cactus graph, 01 natural sciences, Theoretical Computer Science, Combinatorics, Graph power, Outerplanar graph, graph coloring, 0202 electrical engineering, electronic engineering, information engineering, Graph minor, Complement graph, Mathematics, Discrete mathematics, block graph, Cactus graph, 020206 networking & telecommunications, Butterfly graph, claw-free graph, 010201 computation theory & mathematics, proper orientation, Null graph
Abstract: International audience; An orientation of a graph G is proper if two adjacent vertices have different in-degrees. The proper-orientation number − → χ (G) of a graph G is the minimum maximum in-degree of a proper orientation of G. In [1], the authors ask whether the proper orientation number of a planar graph is bounded. We prove that every cactus admits a proper orientation with maximum in-degree at most 7. We also prove that the bound 7 is tight by showing a cactus having no proper orientation with maximum in-degree less than 7. We also prove that any planar claw-free graph has a proper orientation with maximum in-degree at most 6 and that this bound can also be attained.
Published: 2016
Full Text: View/download PDF

9. Overlaying a hypergraph with a graph with bounded maximum degree

Author: Dorian Mazauric, Frédéric Havet, Viet-Ha Nguyen, Rémi Watrigant, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-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), Algorithms, Biology, Structure (ABS), Inria Sophia Antipolis - Méditerranée (CRISAM), Modèles de calcul, Complexité, Combinatoire (MC2), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Inria Sophia Antipolis, 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 (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Hypergraph, Spanning subgraph, Computational complexity theory, 0102 computer and information sciences, Overlay, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], complexité, biologie structurale computationnelle, 01 natural sciences, Combinatorics, biologie structurale computation-nelle, 03 medical and health sciences, graphes, Discrete Mathematics and Combinatorics, [INFO]Computer Science [cs], 030304 developmental biology, Mathematics, 0303 health sciences, algorithm, Applied Mathematics, hypergraphes, graph, Graph, graphe, 010201 computation theory & mathematics, Bounded function, complexity, Hypergraphe, algorithme, algorithmes, computational structural biology
Abstract: International audience; Let G be a graph and H a hypergraph with the same set of vertices and let F be a fixed graph. The graph GF overlays a hyperedge S of H if F is a covering subgraph of the subgraph of G induced by S. The graph GF-overlaying H if F overlays each hyperedge of H. We have analyze the complexity of the following two problems. The first problem, ($∆ ≤ k$) F-OVERLAY, consists in deciding if there is a graph of maximum degree at most k which F overlays a given hypergraph H. This is a special case of the second problem, MAX ($∆ ≤ k$) F-OVERLAY, which, given a hypergraph H and an integer s, consists in deciding whether there is a graph of maximum degree at most k which F overlays at least s hyper edges of H. We prove a polynomial /NP-complete dichotomy for the MAX ($∆ ≤ k$) -F-OVERLAY, and prove the complexity of the problem ($∆ ≤ k$) F-OVERLAY for a large number of pairs (F, k). These two problems model a central problem in computational structural biology: the determination of the contacts between the proteins of a macromolecular assembly. The vertices are the proteins, the hyperedges are the known complexes, the graph F is the generic graph whose edges correspond to the contacts between the proteins of the assembly. Determining the graph G then comes down to finding the contacts between the proteins so that the graph F is a subgraph covering in each hyperedge and so that the degree is bounded (a protein is in contact with a limited number of others proteins). Finally, these problems are of more general interest for network inference problems.; Soient G un graphe et H un hypergraphe avec le même ensemble de sommets et soit F un graphe fixé. Le graphe GF-revouvre une hyperarête S de H si F est un sous-graphe couvrant du sous-graphe de G induit par S. Le graphe GF-revouvre H s’il F-revouvrechaque hyperarête de H. Nous avons analysé la complexité des deux problèmes suivants. Le premier problème, ($∆ ≤ k$) F-OVERLAY, consistè a décider s'il existe un graphe de degré maximum au plus k qui F-revouvre un hypergraphe H donné. C'est un cas particulier du second problème, MAX ($∆ ≤ k$) F-OVERLAY, qui,étant donné un hypergraphe H et un entier s, consistè a décider s'il existe un graphe de degré maximum au plus k qui F-revouvre au moins s hyperarêtes de H. Nous prouvons une dichotomie polynomial/N P-complet pour le problème MAX ($∆ ≤ k$)-F-OVERLAY dépendant de la paire (F, k), et prouvons la complexité du problème ($∆ ≤ k$) F-OVERLAY pour un grand nombre de paires (F, k). Ces deux problèmes modélisent un problème central en biologie structurale computationnelle : la détermination des contacts entre les protéines d'un assemblage macromoléculaire. Les sommets sont les protéines, les hyperarêtes sont les complexes connus, le graphe F est le graphe générique dont les arêtes correspondent aux contacts entre les protéines de l'assemblage. Déterminer le graphe G revient alorsà trouver les contacts entre les protéines de telle sorte que le graphe F soit un sous-graphe couvrant dans chaque hyperarête et de telle sorte que le degré soit borné (une protéine est en contact avec un nombre limité d'autres protéines). Enfin, ces problèmes sont d'intérêt plus général pour les problèmes d'inférence de réseaux.
Published: 2019
Full Text: View/download PDF

10. Subdivisions in digraphs of large out-degree or large dichromatic number

Author: Frédéric Havet, Nathann Cohen, Phablo F. S. Moura, William Lochet, Pierre Aboulker, Stéphan Thomassé, Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-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), Universidade Estadual de Campinas (UNICAMP), Institut Universitaire de France (IUF), Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.), Modèles de calcul, Complexité, Combinatoire (MC2), Laboratoire de l'Informatique du Parallélisme (LIP), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), École normale supérieure - Paris (ENS-PSL), 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 (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Universidade Estadual de Campinas = University of Campinas (UNICAMP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Theoretical Computer Science, Combinatorics, Computer Science::Discrete Mathematics, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Tournament, [INFO]Computer Science [cs], [MATH]Mathematics [math], Subdivision, Mathematics, Transitive relation, Conjecture, Mathematics::Combinatorics, business.industry, Applied Mathematics, Out degree, Digraph, Graph, Computational Theory and Mathematics, 010201 computation theory & mathematics, Geometry and Topology, Combinatorics (math.CO), business
Abstract: In 1985, Mader conjectured the existence of a function $f$ such that every digraph with minimum out-degree at least $f(k)$ contains a subdivision of the transitive tournament of order $k$. This conjecture is still completely open, as the existence of $f(5)$ remains unknown. In this paper, we show that if $D$ is an oriented path, or an in-arborescence (i.e., a tree with all edges oriented towards the root) or the union of two directed paths from $x$ to $y$ and a directed path from $y$ to $x$, then every digraph with minimum out-degree large enough contains a subdivision of $D$. Additionally, we study Mader's conjecture considering another graph parameter. The dichromatic number of a digraph $D$ is the smallest integer $k$ such that $D$ can be partitioned into $k$ acyclic subdigraphs. We show that any digraph with dichromatic number greater than $4^m (n-1)$ contains every digraph with $n$ vertices and $m$ arcs as a subdivision. We show that any digraph with dichromatic number greater than $4^m (n-1)$ contains every digraph with $n$ vertices and $m$ arcs as a subdivision.
Published: 2019

11. $χ$-bounded families of oriented graphs

Author: Pierre Charbit, Frédéric Maffray, Nicolas Bousquet, Frédéric Havet, José Zamora, Jørgen Bang-Jensen, Pierre Aboulker, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), Université Côte d'Azur (UCA)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Nice Sophia Antipolis (... - 2019) (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é Côte d'Azur (UCA)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)-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), University of Southern Denmark (SDU), OC (G-SCOP_OC), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP)-Institut National Polytechnique de Grenoble (INPG)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP)-Institut National Polytechnique de Grenoble (INPG)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Networks, Graphs and Algorithms (GANG), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Universidad Andrés Bello - UNAB (CHILE), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA), 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 (Laboratoire I3S - COMRED), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Department of Mathematics and Computer Science [Odense] (IMADA), Graphes, AlgOrithmes et AppLications (GOAL), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Optimisation Combinatoire (G-SCOP_OC ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Universidad Andrés Bello [Santiago] (UNAB), ANR-13-BS02-0007,Stint,Structures Interdites(2013), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), This work was supported by ANR under contract STINT ANR-13-BS02-0007., COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université Côte d'Azur (UCA)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS), Université Côte d'Azur (UCA), Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), and Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)
Subjects: Transitive relation, Conjecture, Mathematics::Combinatorics, 010102 general mathematics, Induced subgraph, Digraph, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, clique number, Combinatorics, 010201 computation theory & mathematics, chromatic number, Computer Science::Discrete Mathematics, Bounded function, χ-bounded, Discrete Mathematics and Combinatorics, Tournament, Geometry and Topology, Chromatic scale, 0101 mathematics, Mathematics, Computer Science - Discrete Mathematics
Abstract: A famous conjecture of Gy\'arf\'as and Sumner states for any tree $T$ and integer $k$, if the chromatic number of a graph is large enough, either the graph contains a clique of size $k$ or it contains $T$ as an induced subgraph. We discuss some results and open problems about extensions of this conjecture to oriented graphs. We conjecture that for every oriented star $S$ and integer $k$, if the chromatic number of a digraph is large enough, either the digraph contains a clique of size $k$ or it contains $S$ as an induced subgraph. As an evidence, we prove that for any oriented star $S$, every oriented graph with sufficiently large chromatic number contains either a transitive tournament of order $3$ or $S$ as an induced subdigraph. We then study for which sets ${\cal P}$ of orientations of $P_4$ (the path on four vertices) similar statements hold. We establish some positive and negative results., Comment: 27 pages, 4 figures
Published: 2018
Full Text: View/download PDF

12. Complexity dichotomies for the Minimum F -Overlay problem

Author: Frédéric Havet, Dorian Mazauric, Ignasi Sau, Nathann Cohen, Rémi Watrigant, Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), 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 (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA), Algorithms, Biology, Structure (ABS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Modèles de calcul, Complexité, Combinatoire (MC2), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), ANR-16-CE40-0028,DE-MO-GRAPH,Décomposition de Modèles Graphiques(2016), Graphes, Algorithmes et Combinatoire (LRI) (GALaC - LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Universidade Federal do Ceará = Federal University of Ceará (UFC), Projet de Recherche Exploratoire Inria: Improving inference algorithms for macromolecular structure determination, ANR-13-BS02-0007,Stint,Structures Interdites(2013), CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS)-CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), This work was partially funded by ‘Projet de Recherche Exploratoire’, Inria, Improving inference algorithms for macromolecular structure determination, Inria Sophia Antipolis, CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: FOS: Computer and information sciences, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Hypergraph, Spanning subgraph, Dichotomy, Subgraph isomorphism problem, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Parameterized complexity, 0102 computer and information sciences, 02 engineering and technology, Overlay, Computational Complexity (cs.CC), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Theoretical Computer Science, Combinatorics, Computer Science - Data Structures and Algorithms, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, Induced subgraph isomorphism problem, Data Structures and Algorithms (cs.DS), [INFO]Computer Science [cs], ComputingMilieux_MISCELLANEOUS, Mathematics, Discrete mathematics, Complete graph, 020206 networking & telecommunications, NP-completeness, Minimum F-Overlay Problem, Computer Science - Computational Complexity, Computational Theory and Mathematics, 010201 computation theory & mathematics, Fixed-parameter tractability
Abstract: International audience; For a (possibly infinite) fixed family of graphs F, we say that a graph G overlays F on a hypergraph H if V (H) is equal to V (G) and the subgraph of G induced by every hyperedge of H contains some member of F as a spanning subgraph. While it is easy to see that the complete graph on |V (H)| overlays F on a hypergraph H whenever the problem admits a solution, the Minimum F-Overlay problem asks for such a graph with the minimum number of edges. This problem allows to generalize some natural problems which may arise in practice. For instance, if the family F contains all connected graphs, then Minimum F-Overlay corresponds to the Minimum Connectivity Inference problem (also known as Subset Interconnection Design problem) introduced for the low-resolution reconstruction of macro-molecular assembly in structural biology, or for the design of networks. Our main contribution is a strong dichotomy result regarding the polynomial vs. NP-hard status with respect to the considered family F. Roughly speaking, we show that the easy cases one can think of (e.g. when edge-less graphs of the right sizes are in F, or if F contains only cliques) are the only families giving rise to a polynomial problem: all others are NP-complete. We then investigate the parameterized complexity of the problem and give similar sufficient conditions on F that give rise to W[1]-hard, W[2]-hard or FPT problems when the parameter is the size of the solution. This yields an FPT/W[1]-hard dichotomy for a relaxed problem , where every hyperedge of H must contain some member of F as a (non necessarily spanning) subgraph.
Published: 2018
Full Text: View/download PDF

13. Complexity Dichotomies for the Minimum $$\mathcal {F}$$-Overlay Problem

Author: Dorian Mazauric, Rémi Watrigant, Nathann Cohen, Ignasi Sau, and Frédéric Havet
Subjects: Combinatorics, Hypergraph, Spanning subgraph, 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, Complete graph, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, Overlay, 01 natural sciences, Graph, Mathematics
Abstract: For a (possibly infinite) fixed family of graphs $\mathcal {F}$, we say that a graph G overlays $\mathcal {F}$ on a hypergraph H if V(H) is equal to V(G) and the subgraph of G induced by every hyperedge of H contains some member of $\mathcal {F}$ as a spanning subgraph. While it is easy to see that the complete graph on |V(H)| overlays $\mathcal {F}$ on a hypergraph H whenever the problem admits a solution, the Minimum $\mathcal {F}$-Overlay problem asks for such a graph with the minimum number of edges. This problem allows to generalize some natural problems which may arise in practice. For instance, if the family $\mathcal {F}$ contains all connected graphs, then Minimum $\mathcal {F}$-Overlay corresponds to the Minimum Connectivity Inference problem (also known as Subset Interconnection Design problem) introduced for the low-resolution reconstruction of macro-molecular assembly in structural biology, or for the design of networks.
Published: 2018
Full Text: View/download PDF

14. Tournaments and Semicomplete Digraphs

Author: Jørgen Bang-Jensen, Frédéric Havet, Bang-Jensen, Jørgen, Gutin, Gregory, COMUE Université Côte d'Azur (2015-2019) (COMUE UCA), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-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), Department of Mathematics and Computer Science [Odense] (IMADA), University of Southern Denmark (SDU), 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 (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
Subjects: Class (set theory), Mathematics::Combinatorics, 010102 general mathematics, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Mathematical proof, 01 natural sciences, Combinatorics, Range (mathematics), Cover (topology), 010201 computation theory & mathematics, Computer Science::Discrete Mathematics, Order (group theory), 0101 mathematics, ComputingMilieux_MISCELLANEOUS, Superclass, Mathematics
Abstract: The class of tournaments is by far the most well-studied class of digraphs with many deep and important results. Since Moon’s pioneering book in 1968 [146], the study of tournaments and their properties has flourished and research on tournaments is still a very active area. Often this research deals with the superclass of semicomplete digraphs which are digraphs with no pair of non-adjacent vertices (that is, contrary to tournaments, we allow directed cycles of length 2). In this chapter we cover a very broad range of results on tournaments and semicomplete digraphs from classical to very recent ones. In order to stimulate further research, we not only list a number of open problems, but also give a number of proofs which illustrate the diversity of proof techniques that have been applied. These range from elementary to quite advanced.
Published: 2018
Full Text: View/download PDF

15. Steinberg-like theorems for backbone colouring

Author: Frédéric Havet, Júlio Araújo, Mathieu Schmitt, Parallelism, Graphs and Optimization Research Group (ParGO), Universidade Federal do Ceará = Federal University of Ceará (UFC), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-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), École normale supérieure - Lyon (ENS Lyon), 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 (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), École normale supérieure de Lyon (ENS de Lyon), and CNRS-FUNCAP GAIATO
Subjects: Graph colouring, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Planar Graph, Combinatorics, symbols.namesake, Steinberg's Conjecture, Subgroup, Graph power, Graph minor, Discrete Mathematics and Combinatorics, Graph toughness, 0101 mathematics, ComputingMilieux_MISCELLANEOUS, Mathematics, Discrete mathematics, Connected component, Graph Colouring, Applied Mathematics, 010102 general mathematics, Backbone Colouring, Graph, Planar graph, New digraph reconstruction conjecture, Edge-transitive graph, 010201 computation theory & mathematics, symbols, Bound graph, Graph factorization
Abstract: A function f : V ( G ) → { 1 , … , k } is a (proper) k -colouring of G if ∣ f ( u ) − f ( v ) ∣ ≥ 1 , for every edge u v ∈ E ( G ) . The chromatic number χ ( G ) is the smallest integer k for which there exists a proper k -colouring of G . Given a graph G and a subgraph H of G , a circular q -backbone k -colouring f of ( G , H ) is a k -colouring of G such that q ≤ ∣ f ( u ) − f ( v ) ∣ ≤ k − q , for each edge u v ∈ E ( H ) . The circular q -backbone chromatic number of a graph pair ( G , H ) , denoted CBC q ( G , H ) , is the minimum k such that ( G , H ) admits a circular q -backbone k -colouring. Inspired by Steinberg’s conjecture, we conjecture that if G is a planar graph containing no cycles on 4 or 5 vertices and H ⊆ G is a forest, then CBC 2 ( G , H ) ≤ 6 . In this work, we first show that if G is a planar graph containing no cycle on 4 or 5 vertices and H ⊆ G is a forest, then CBC 2 ( G , H ) ≤ 7 . Then, we prove that if H ⊆ G is a forest whose connected components are paths, then CBC 2 ( G , H ) ≤ 6 .
Published: 2018
Full Text: View/download PDF

16. On the Complexity of Compressing Two Dimensional Routing Tables with Order

Author: Joanna Moulierac, Frédéric Havet, Frédéric Giroire, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-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), ANR-13-BS02-0007,Stint,Structures Interdites(2013), 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 (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
Subjects: Discrete mathematics, Reduction (recursion theory), General Computer Science, Applied Mathematics, Routing table, Order (ring theory), Approximation algorithm, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, Function (mathematics), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Computer Science Applications, Combinatorics, Integer, 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, Routing (electronic design automation), Mathematics
Abstract: Motivated by routing in telecommunication network using Software Defined Network (SDN) technologies, we consider the following problem of finding short routing lists using aggregation rules. We are given a set of communications $$\mathcal {X}$$ , which are distinct pairs $$(s,t)\subseteq S\times T$$ , (typically S is the set of sources and T the set of destinations), and a port function $$\pi :\mathcal {X} \rightarrow P$$ where P is the set of ports. A routing list $$\mathcal {R}$$ is an ordered list of triples which are of the form (s, t, p), $$(*,t,p)$$ , $$(s,*,p)$$ or $$(*,*,p)$$ with $$s\in S$$ , $$t\in T$$ and $$p\in P$$ . It routes the communication (s, t) to the port $$r(s,t) =p$$ which appears on the first triple in the list $$\mathcal {R}$$ that is of the form (s, t, p), $$(*,t,p)$$ , $$(s,*,p)$$ or $$(*,*,p)$$ . If $$r(s,t)=\pi (s,t)$$ , then we say that (s, t) is properly routed by $$\mathcal {R}$$ and if all communications of $$\mathcal {X}$$ are properly routed, we say that $$\mathcal {R}$$ emulates $$(\mathcal {X}, \pi )$$ . The aim is to find a shortest routing list emulating $$(\mathcal {X}, \pi )$$ . In this paper, we carry out a study of the complexity of the two dual decision problems associated to it. Given a set of communication $$\mathcal {X}$$ , a port function $$\pi $$ and an integer k, the first one called Routing List (resp. the second one, called List Reduction) consists in deciding whether there is a routing list emulating $$(\mathcal {X}, \pi )$$ of size at most k (resp. $$|\mathcal {X}| -k$$ ). We prove that both problems are NP-complete. We then give a 3-approximation for List Reduction, which can be generalized to higher dimensions. We also give a 4-approximation for Routing List in the fundamental case when there are only two ports (i.e. $$|P|=2$$ ), $$\mathcal {X}=S\times T$$ and $$|S|=|T|$$ .
Published: 2018
Full Text: View/download PDF

17. Bispindle in strongly connected digraphs with large chromatic number

Author: Raul Lopes, William Lochet, Frédéric Havet, Nathann Cohen, Graphes, Algorithmes et Combinatoire (LRI) (GALaC - LRI), Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), 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 (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Institut National de Recherche en Informatique et en Automatique (Inria), Parallelism, Graphs and Optimization Research Group (ParGO), Universidade Federal do Ceará = Federal University of Ceará (UFC), ANR-13-BS02-0007,Stint,Structures Interdites(2013), Université Nice Sophia Antipolis (... - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS)
Subjects: Strongly connected component, business.industry, Applied Mathematics, Digraph, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, Disjoint sets, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Combinatorics, Integer, 010201 computation theory & mathematics, chromatic number, subdivision, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, Chromatic scale, business, Mathematics, Subdivision
Abstract: A ( k 1 + k 2 )-bispindle is the union of k1 (x, y)-dipaths and k2 (y, x)-dipaths, all these dipaths being pairwise internally disjoint. Recently, Cohen et al. showed that for every (2 + 0)-bispindle B, there exists an integer k such that every strongly connected digraph with chromatic number greater than k contains a subdivision of B. We investigate generalisations of this result by first showing constructions of strongly connected digraphs with large chromatic number without any ( 3 + 0 )-bispindle or ( 2 + 2 )-bispindle. Then we show that for any k, there exists γ k such that every strongly connected digraph with chromatic number greater than γ k contains a ( 2 + 1 )-bispindle with the (y, x)-dipath and one of the (x, y)-dipaths of length at least k.
Published: 2017
Full Text: View/download PDF

18. Out-degree reducing partitions of digraphs

Author: Joergen Bang-Jensen, Frédéric Havet, Anders Yeo, Stéphane Bessy, Department of Mathematics and Computer Science [Odense] (IMADA), University of Southern Denmark (SDU), Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), 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 (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Danish research council, grant number 1323-00178B, Labex UCN@Sophia, OSMO project, Occitanie regional council, ANR-13-BS02-0007,Stint,Structures Interdites(2013), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: FOS: Computer and information sciences, Vertex (graph theory), Discrete Mathematics (cs.DM), General Computer Science, Maximum out-degree reducing partition, Polynomial algorithm, 0102 computer and information sciences, Characterization (mathematics), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Theoretical Computer Science, Combinatorics, Integer, Computer Science::Discrete Mathematics, FOS: Mathematics, Mathematics - Combinatorics, 05C20, 0101 mathematics, Mathematics, NP-complete, Discrete mathematics, Mathematics::Combinatorics, 2-partition, 010102 general mathematics, Out degree, Digraph, 010201 computation theory & mathematics, Combinatorics (math.CO), Computer Science - Discrete Mathematics
Abstract: Let $k$ be a fixed integer. We determine the complexity of finding a $p$-partition $(V_1, \dots, V_p)$ of the vertex set of a given digraph such that the maximum out-degree of each of the digraphs induced by $V_i$, ($1\leq i\leq p$) is at least $k$ smaller than the maximum out-degree of $D$. We show that this problem is polynomial-time solvable when $p\geq 2k$ and ${\cal NP}$-complete otherwise. The result for $k=1$ and $p=2$ answers a question posed in \cite{bangTCS636}. We also determine, for all fixed non-negative integers $k_1,k_2,p$, the complexity of deciding whether a given digraph of maximum out-degree $p$ has a $2$-partition $(V_1,V_2)$ such that the digraph induced by $V_i$ has maximum out-degree at most $k_i$ for $i\in [2]$. It follows from this characterization that the problem of deciding whether a digraph has a 2-partition $(V_1,V_2)$ such that each vertex $v\in V_i$ has at least as many neighbours in the set $V_{3-i}$ as in $V_i$, for $i=1,2$ is ${\cal NP}$-complete. This solves a problem from \cite{kreutzerEJC24} on majority colourings., 11 pages, 1 figure
Published: 2017
Full Text: View/download PDF

19. Bipartite spanning sub(di)graphs induced by 2-partitions

Author: Jørgen Bang-Jensen, Anders Yeo, Frédéric Havet, Stéphane Bessy, University of Southern Denmark (SDU), Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-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), Occitanie regional council. Grant Number: OSMO- Labex UCN©Sophia- Danish Research Council. Grant Number: 1323‐00178B, ANR-13-BS02-0007,Stint,Structures Interdites(2013), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), 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 (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
Subjects: FOS: Computer and information sciences, Strongly connected component, Discrete Mathematics (cs.DM), eulerian, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, 2-partition, spanning bipartite subdigraph, Combinatorics, symbols.namesake, Computer Science::Discrete Mathematics, Spanning bipartite subdigraph, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, 05C20, 0101 mathematics, Nuclear Experiment, Eulerian, Mathematics, Mathematics::Combinatorics, Minimum out-degree, 2-partition, 010102 general mathematics, strong spanning subdigraph, Strong spanning subdigraph, Digraph, Eulerian path, Graph, Vertex (geometry), 010201 computation theory & mathematics, Bipartite graph, symbols, minimum out-degree, Geometry and Topology, Combinatorics (math.CO), Computer Science - Discrete Mathematics
Abstract: For a given $2$-partition $(V_1,V_2)$ of the vertices of a (di)graph $G$, we study properties of the spanning bipartite subdigraph $B_G(V_1,V_2)$ of $G$ induced by those arcs/edges that have one end in each $V_i$. We determine, for all pairs of non-negative integers $k_1,k_2$, the complexity of deciding whether $G$ has a 2-partition $(V_1,V_2)$ such that each vertex in $V_i$ has at least $k_i$ (out-)neighbours in $V_{3-i}$. We prove that it is ${\cal NP}$-complete to decide whether a digraph $D$ has a 2-partition $(V_1,V_2)$ such that each vertex in $V_1$ has an out-neighbour in $V_2$ and each vertex in $V_2$ has an in-neighbour in $V_1$. The problem becomes polynomially solvable if we require $D$ to be strongly connected. We give a characterisation, based on the so-called strong component digraph of a non-strong digraph of the structure of ${\cal NP}$-complete instances in terms of their strong component digraph. When we want higher in-degree or out-degree to/from the other set the problem becomes ${\cal NP}$-complete even for strong digraphs. A further result is that it is ${\cal NP}$-complete to decide whether a given digraph $D$ has a $2$-partition $(V_1,V_2)$ such that $B_D(V_1,V_2)$ is strongly connected. This holds even if we require the input to be a highly connected eulerian digraph., Comment: 17 pages, 4 figures
Published: 2017
Full Text: View/download PDF

20. Identifying codes for infinite triangular grids with a finite number of rows

Author: Frédéric Havet, Rudini Menezes Sampaio, Rennan Dantas, Parallelism, Graphs and Optimization Research Group (ParGO), Universidade Federal do Ceará = Federal University of Ceará (UFC), 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 (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), INRIA Sophia Antipolis - I3S, FUNCAP/CNRS project GAIATO INC-0083- 00047.01.00/13, ANR-13-BS02-0007,Stint,Structures Interdites(2013), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA), and FUNCAP-CNRS project GAIATO
Subjects: Vertex (graph theory), Discrete mathematics, grille, Discharging method, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, Triangular grid, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, grid, Graph, Theoretical Computer Science, Combinatorics, identifying code, 010201 computation theory & mathematics, méthode de déchargement, code identifiant, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, discharging method, Row, Finite set, Minimum density, Mathematics
Abstract: Let $\mathcal{G}_T$ be the infinite triangular grid. For any positive integer $k$, we denote by $T_k$ the subgraph of $\mathcal{G}_T$ induced by the vertex set $\{(x,y)\in\mathbb{Z}\times[k]\}$.A set $C\subset V(G)$ is an {\it identifying code} in a graph $G$ if for all $v\in V(G)$, $N[v]\cap C\neq \emptyset$, and for all $u,v\in V(G)$, $N[u]\cap C\neq N[v]\cap C$, where $N[x]$ denotes the closed neighborhood of $x$ in $G$.The minimum density of an identifying code in $G$ is denoted by $d^*(G)$.In this paper, we prove that $d^*(T_1)=d^*(T_2)=1/2$, $d^*(T_3)=d^*(T_4)=1/3$, $d^*(T_5)=3/10$, $d^*(T_6)=1/3$ and $d^*(T_k)=1/4+1/(4k)$ for every $k\geq 7$ odd. Moreover, we prove that $1/4+1/(4k)\leq d^*(T_k)\leq 1/4+1/(2k)$ for every $k\geq 8$ even.; Soit $\mathcal{G}_T$ la grille triangulaire infinie. Pour pout entier strictement positif $k$, nous notons $T_k$ le sous-graphe de $\mathcal{G}_T$ induit par l'ensemble des sommets $\{(x,y)\in\mathbb{Z}\times[k]\}$.Un ensemble $C\subset V(G)$ est un {\it code identifiant} d'un graphe $G$ si pour tout $v\in V(G)$, $N[v]\cap C\neq \emptyset$, et pour tout $u,v\in V(G)$, $N[u]\cap C\neq N[v]\cap C$, o\`u $N[x]$ est le voisinage ferm\'e de $x$ dans $G$.La densit\'e minimum d'un code identifiant de $G$ est not\'ee $d^*(G)$.Dans ce rapport, nous montrons que $d^*(T_1)=d^*(T_2)=1/2$, $d^*(T_3)=d^*(T_4)=1/3$, $d^*(T_5)=3/10$, $d^*(T_6)=1/3$ et $d^*(T_k)=1/4+1/(4k)$ pour tout $k\geq 7$ impair. De plus, nous montrons que $1/4+1/(4k)\leq d^*(T_k)\leq 1/4+1/(2k)$ pour tout $k\geq 8$ pair.
Published: 2016
Full Text: View/download PDF

21. Finding good 2-partitions of digraphs II. Enumerable properties

Author: Nathann Cohen, Jørgen Bang-Jensen, Frédéric Havet, Department of Mathematics and Computer Science [Odense] (IMADA), University of Southern Denmark (SDU), Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), 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 (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Université Nice Sophia Antipolis (... - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS)
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Strongly connected component, General Computer Science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, Disjoint sets, Vertex partition, 01 natural sciences, Polynomial, Out-branching, Theoretical Computer Science, Combinatorics, Computer Science::Discrete Mathematics, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Partition (number theory), Tournament, 0101 mathematics, Feedback vertex set, Mathematics, NP-complete, Acyclic, Discrete mathematics, Semicomplete digraph, 010102 general mathematics, Digraph, Oriented, Has property, 2-Partition, 010201 computation theory & mathematics, Minimum degree, Splitting digraphs, Partition
Abstract: International audience; We continue the study, initiated in [3], of the complexity of deciding whether a given digraph D has a vertex-partition into two disjoint subdigraphs with given structural properties and given minimum cardinality. Let EE be the following set of properties of digraphs: E=E={strongly connected, connected, minimum out-degree at least 1, minimum in-degree at least 1, minimum semi-degree at least 1, minimum degree at least 1, having an out-branching, having an in-branching}. In this paper we determine, for all choices of P1,P2P1,P2 from EE and all pairs of fixed positive integers k1,k2k1,k2, the complexity of deciding whether a digraph has a vertex partition into two digraphs D1,D2D1,D2 such that DiDi has property PiPi and |V(Di)|≥ki|V(Di)|≥ki, i=1,2i=1,2. We also classify the complexity of the same problems when restricted to strongly connected digraphs. The complexity of the analogous problems when P1∈HP1∈H and P2∈H∪EP2∈H∪E, where H=H={acyclic, complete, arc-less, oriented (no 2-cycle), semicomplete, symmetric, tournament} were completely characterized in [3].
Published: 2016
Full Text: View/download PDF

22. New Bounds on the Grundy Number of Products of Graphs

Author: Frédéric Havet, András Gyárfás, Cláudia Linhares Sales, Victor Campos, and Frédéric Maffray
Subjects: Discrete mathematics, 010102 general mathematics, Graph theory, 0102 computer and information sciences, Complete coloring, 01 natural sciences, Graph, Greedy coloring, Combinatorics, 010201 computation theory & mathematics, Grundy number, Discrete Mathematics and Combinatorics, Geometry and Topology, 0101 mathematics, Greedy algorithm, Mathematics
Abstract: The Grundy number of a graph G is the largest k such that G has a greedy k-coloring, that is, a coloring with k colors obtained by applying the greedy algorithm according to some ordering of the vertices of G. In this article, we give new bounds on the Grundy number of the product of two graphs. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:78–88, 2012 © 2012 Wiley Periodicals, Inc.
Published: 2012
Full Text: View/download PDF

23. Finding an induced subdivision of a digraph

Author: Frédéric Havet, Nicolas Trotignon, Jørgen Bang-Jensen, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), 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 (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Department of Mathematics and Computer Science [Odense] (IMADA), University of Southern Denmark (SDU), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Financial support from the Danish National Science research council (FNU) (under grant no. 09-066741)., Electronic Notes on Discrete Mathematics, ANR-09-BLAN-0159,AGAPE,Algorithmes de graphes parametres et exacts(2009), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and INRIA
Subjects: FOS: Computer and information sciences, Polynomial, Discrete Mathematics (cs.DM), General Computer Science, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Mathematical proof, 01 natural sciences, Theoretical Computer Science, Combinatorics, 3-SAT, Computer Science::Discrete Mathematics, FOS: Mathematics, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, 05C85, Mathematics, Subdivision, Discrete mathematics, Mathematics::Combinatorics, business.industry, Applied Mathematics, 020206 networking & telecommunications, Digraph, Graph, NP-completeness, induced paths and cycles, 010201 computation theory & mathematics, Combinatorics (math.CO), linkings, business, Computer Science(all), Computer Science - Discrete Mathematics, digraphs
Abstract: International audience; We consider the following problem for oriented graphs and digraphs: Given an oriented graph (digraph) G, does it contain an induced subdivision of a prescribed digraph D? The complexity of this problem depends on D and on whether G must be an oriented graph or is allowed to contain 2-cycles. We give a number of examples of polynomial instances as well as several NP-completeness proofs.
Published: 2012
Full Text: View/download PDF

24. Complexity of (p,1)-total labelling

Author: Frédéric Havet and Stéphan Thomassé
Subjects: Discrete mathematics, Vertex (graph theory), Applied Mathematics, 010102 general mathematics, 0102 computer and information sciences, 01 natural sciences, Upper and lower bounds, Graph, Combinatorics, 010201 computation theory & mathematics, Labelling, Bipartite graph, Discrete Mathematics and Combinatorics, Cubic graph, Regular graph, 0101 mathematics, Graph labelling, Mathematics
Abstract: A (p,1)-total labelling of a graph G=(V,E) is a total colouring L from V@?E into {0,...,l} such that |L(v)-L(e)|>=p whenever an edge e is incident to a vertex v. The minimum l for which G admits a (p,1)-total labelling is denoted by @l"p(G). The case p=1 corresponds to the usual notion of total colouring, which is NP-hard to compute even for cubic bipartite graphs [C.J. McDiarmid, A. Sanchez-Arroyo, Total colouring regular bipartite graphs is NP-hard, Discrete Math. 124 (1994), 155-162]. In this paper we assume p>=2. It is easy to show that @l"p(G)>=@D+p-1, where @D is the maximum degree of G. Moreover, when G is bipartite, @D+p is an upper bound for @l"p(G), leaving only two possible values. In this paper, we completely settle the computational complexity of deciding whether @l"p(G) is equal to @D+p-1 or to @D+p when G is bipartite. This is trivial when @D@?p, polynomial when @D=3 and p=2, and NP-complete in the remaining cases.
Published: 2009
Full Text: View/download PDF

25. Choosability of the square of planar subcubic graphs with large girth

Author: Frédéric Havet, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), 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 (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: Discrete mathematics, 010102 general mathematics, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Planar graph, Theoretical Computer Science, Choice number, Combinatorics, symbols.namesake, Planar, List colouring, 010201 computation theory & mathematics, Square of a graph, symbols, Discrete Mathematics and Combinatorics, 0101 mathematics, Bounded density, Mathematics
Abstract: International audience; We show that the choice number of the square of a subcubic graph with maximum average degree less than 18/7 is at most 6. As a corollary, we get that the choice number of the square of a subcubic planar graph with girth at least 9 is at most 6. We then show that the choice number of the square of a subcubic planar graph with girth at least 13 is at most 5.
Published: 2009
Full Text: View/download PDF

26. Hoàng–Reed conjecture holds for tournaments

Author: Stéphan Thomassé, Frédéric Havet, and Anders Yeo
Subjects: Discrete mathematics, Class (set theory), Conjecture, 010102 general mathematics, Structure (category theory), Digraph, 0102 computer and information sciences, Directed graph, 01 natural sciences, Theoretical Computer Science, Combinatorics, 010201 computation theory & mathematics, Triangle structure, Discrete Mathematics and Combinatorics, Tournament, 0101 mathematics, Mathematics
Abstract: Hoang-Reed conjecture asserts that every digraph D has a collection C of circuits C"1,...,C"@d"^"+, where @d^+ is the minimum outdegree of D, such that the circuits of C have a forest-like structure. Formally, |V(C"i)@?(V(C"1)@?...@?V(C"i"-"1))|=
Published: 2008
Full Text: View/download PDF

27. Finding good 2-partitions of digraphs I. Hereditary properties

Author: Frédéric Havet, Jørgen Bang-Jensen, Department of Mathematics and Computer Science [Odense] (IMADA), University of Southern Denmark (SDU), 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 (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Labex UCN@Sophia, Sophia Antipolis, ANR-13-BS02-0007,Stint,Structures Interdites(2013), Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: Strongly connected component, General Computer Science, polynomial, 0102 computer and information sciences, Vertex partition, Disjoint sets, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, semicomplete digraph, out-branching, Theoretical Computer Science, Combinatorics, Computer Science::Discrete Mathematics, Partition (number theory), Tournament, splitting digraphs, 0101 mathematics, Mathematics, minimum degree, NP-complete, Discrete mathematics, oriented, 2-partition, 010102 general mathematics, acyclic, Digraph, feedback vertex set, partition, tournament, Has property, 010201 computation theory & mathematics, Feedback vertex set
Abstract: We study the complexity of deciding whether a given digraph D has a vertex-partition into two disjoint subdigraphs with given structural properties. Let H and E denote the following two sets of natural properties of digraphs: H = {acyclic, complete, arcless, oriented (no 2-cycle), semicomplete, symmetric, tournament} and E = {strongly connected, connected, minimum out-degree at least 1, minimum in-degree at least 1, minimum semi-degree at least 1, minimum degree at least 1, having an out-branching, having an in-branching}. In this paper, we determine the complexity of deciding, for any fixed pair of positive integers k 1 , k 2 , whether a given digraph has a vertex partition into two digraphs D 1 , D 2 such that | V ( D i ) | ź k i and D i has property P i for i = 1 , 2 when P 1 ź H and P 2 ź H ź E . We also classify the complexity of the same problems when restricted to strongly connected digraphs.The complexity of the 2-partition problems where both P 1 and P 2 are in E is determined in the companion paper 2.
Published: 2016
Full Text: View/download PDF

28. Subidvisions de cycles orientés dans les graphes dirigés de fort nombre chromatique

Author: Nicolas Nisse, Frédéric Havet, Nathann Cohen, William Lochet, Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), 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 (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA), Modèles de calcul, Complexité, Combinatoire (MC2), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), LRI-GALAC, ANR-13-BS02-0007,Stint,Structures Interdites(2013), École normale supérieure de Lyon (ENS de Lyon), LRI - CNRS, University Paris-Sud, LIP - ENS Lyon, INRIA Sophia Antipolis - I3S, Graphes, Algorithmes et Combinatoire (LRI) (GALaC - LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), École normale supérieure - Lyon (ENS Lyon), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-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), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS)-CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS)
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Strongly connected component, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, Orientation (graph theory), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Combinatorics, Computer Science::Discrete Mathematics, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Chromatic scale, 0101 mathematics, Mathematics, Subdivision, Mathematics::Combinatorics, business.industry, 010102 general mathematics, Digraph, Arbitrarily large, 010201 computation theory & mathematics, Geometry and Topology, Combinatorics (math.CO), business
Abstract: An {\it oriented cycle} is an orientation of a undirected cycle.We first show that for any oriented cycle $C$, there are digraphs containing no subdivision of $C$ (as a subdigraph) and arbitrarily large chromatic number.In contrast, we show that for any $C$ is a cycle with two blocks, every strongly connected digraph with sufficiently large chromatic number contains a subdivision of $C$. We prove a similar result for the antidirected cycle on four vertices (in which two vertices have out-degree $2$ and two vertices have in-degree $2$).; Un {\it cycle orienté} est l'orientation d'un cycle. Nous prouvons que pour tout cycle orienté $C$ il existe des graphes dirigés sans subdivisions de $C$ (en tant que sous graphe) et de nombre chromatique arbitrairement grand. Par ailleurs, nous prouvons que pour tout cycle a deux bloques, tout graphe dirigé fortement connexe de nombre chromatique suffisamment grand contient une subdivision de $C$. Nous prouvons aussi un resultat semblable sur le cycle antidirigé de taille quatre (avec deux sommets de degré sortant $2$ et deux sommets de degré entrant $2$).
Published: 2016
Full Text: View/download PDF

29. Minimum-Density Identifying Codes in Square Grids

Author: Frédéric Havet, Myriam Preissmann, Marwane Bouznif, Optimisation Combinatoire (G-SCOP_OC ), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), 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 (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Riccardo Dondi, ANR-13-BS02-0007,Stint,Structures Interdites(2013), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), and INRIA Sophia Antipolis - I3S
Subjects: Square tiling, Discrete mathematics, Discharging method, Neighbourhood (graph theory), square grid, 010103 numerical & computational mathematics, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Vertex (geometry), Combinatorics, identifying code, 010201 computation theory & mathematics, discharging method, 0101 mathematics, Minimum density, Mathematics
Abstract: An identifying code in a graph $G$ is a subset of vertices with the property that for each vertex $v \in V(G)$, the collection of elements of $C$ at distance at most $1$ from $v$ is non-empty and distinct from the collection of any other vertex. We consider the minimum density $d^*({\cal S}_k)$ of an identifying code in the square grid ${\cal S}_k$ of height $k$ (i.e. with vertex set $ \mathbb{Z} \times \{1, \dots , k\}$).Using the Discharging Method, we prove $\displaystyle \frac{7}{20} + \frac{1}{20k} \leq d^*({\cal S}_k) \leq \min \left\{\frac{2}{5}, \frac{7}{20} + \frac{3}{10k} \right\}$, and $\displaystyle d^*({\cal S}_3) =\frac{3}{7}$.
Published: 2016
Full Text: View/download PDF

30. Complexity of greedy edge-colouring

Author: A. Karolinna Maia, Min-Li Yu, Frédéric Havet, 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 (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Universidade Federal do Ceará = Federal University of Ceará (UFC), University of the Fraser Valley (UFV), CNRS-FUNCAP GAIATO, Université Nice Sophia Antipolis (... - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS)
Subjects: Mathematical optimization, General Computer Science, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Data structure, 01 natural sciences, Graph, law.invention, Combinatorics, Greedy coloring, 010201 computation theory & mathematics, law, Line graph, 0202 electrical engineering, electronic engineering, information engineering, NP-complete, Greedy algorithm, Computer Science(all), Mathematics
Abstract: International audience; The Grundy index of a graph G = (V, E) is the greatest number of colours that the greedy edge-colouring algorithm can use on G. We prove that the problem of determining the Grundy index of a graph G = (V, E) is NP-hard for general graphs. We also show that this problem is polynomial-time solvable for caterpillars. More specifically, we prove that the Grundy index of a caterpillar is (G) or (G) + 1 and present a polynomial-time algorithm to determine it exactly.
Published: 2015
Full Text: View/download PDF

31. Compressing two-dimensional routing tables with order

Author: Frédéric Havet, Joanna Moulierac, Frédéric Giroire, 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 (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), ANR-11-LABX-0031,UCN@SOPHIA,Réseau orienté utilisateur(2011), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), INRIA Sophia Antipolis, INRIA, and ANR-13-BS02-0007,Stint,Structures Interdites(2013)
Subjects: Dynamic Source Routing, Theoretical computer science, Equal-cost multi-path routing, FPT, Geographic routing, 0102 computer and information sciences, 02 engineering and technology, Source routing, 01 natural sciences, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, compact tables, approximation algorithm, routing tables, Mathematics, Static routing, Applied Mathematics, Path vector protocol, DSRFLOW, 020206 networking & telecommunications, Routing domain, routing, 010201 computation theory & mathematics, complexity, software defined networks
Abstract: International audience; A communication in a network is a pair of nodes (s, t). The node s is called the source source and t the destination. A communication set is a set of distinct communications, i.e. two communications might have the same source or the same destination, but they cannot have both same source and same destination. A routing of a communication (s, t) is a path in the network from s to t. A routing of a communication set is a union of routings of its communications. At each node, there is a set X of communications whose routing path goes through this node. The node needs to be able to find for each communication (s,t) in X, the port that the routing path of (s,t) uses to leave it. An easy way of doing it is to store the list of all triples (s,t,k), where (s, t) ∈ X and k is the port used by the (s, t)-path to leave the node. Such triples are called communication triples. However, such a list might be very large. Motivated by routing in telecommunication network using Software Defined Network Technologies, we consider the problem of compacting this list using aggregation rules. Indeed, SDN routers use specific memory which is expensive and of small capacity. Hence, in addition, we can use some additional triples, called ∗-triples. As an example, a t-destination triple (∗, t, p), means that every communication with destination t leaves on port p. We carry out in this work a study of the problem complexity, providing results of NP-completeness, of Fixed-Parameter Tractability and approximation algorithms.
Published: 2015

32. REPARTITORS, SELECTORS AND SUPERSELECTORS

Author: Frédéric Havet
Subjects: Vertex (graph theory), Discrete mathematics, 021103 operations research, Computer Networks and Communications, 0211 other engineering and technologies, 0102 computer and information sciences, 02 engineering and technology, Disjoint sets, 01 natural sciences, Graph, Combinatorics, 010201 computation theory & mathematics, ComputingMilieux_MISCELLANEOUS, Mathematics
Abstract: An (n, p, f)-network G is a graph (V, E) where the vertex set V is partitioned into four subsets [Formula: see text] and [Formula: see text] called respectively the priorities, the ordinary inputs, the outputs and the switches, satisfying the following constraints: there are p priorities, n - p ordinary inputs and n + f outputs; each priority, each ordinary input and each output is connected to exactly one switch; switches have degree at most 4. An (n, p, f)-network is an (n, p, f)-repartitor if for any disjoint subsets [Formula: see text] and [Formula: see text] of [Formula: see text] with [Formula: see text] and [Formula: see text], there exist in G, n edge-disjoint paths, p of them from [Formula: see text] to [Formula: see text] and the n - p others joining [Formula: see text] to [Formula: see text]. The problem is to determine the minimum number R(n, p, f) of switches of an (n, p, f)-repartitor and to construct a repartitor with the smallest number of switches. In this paper, we show how to build general repartitors from (n, 0, f)-repartitors also called (n, n + f)-selectors. We then consrtuct selectors using more powerful networks called superselectors. An (n, 0, 0)-network is an n-superselector if for any subsets [Formula: see text] and [Formula: see text] with [Formula: see text], there exist in G, [Formula: see text] edge-disjoint paths joining [Formula: see text] to [Formula: see text]. We show that the minimum number of switches of an n-superselector S+ (n) is at most 17n + O(log(n)). We then deduce that [Formula: see text] if [Formula: see text], R(n, p, f) ≤ 18n + 34f + O( log (n + f)), if [Formula: see text] and [Formula: see text] if [Formula: see text]. Finally, we give lower bounds for R(n, 0, f) and S+ (n) and show optimal networks for small value of n.
Published: 2006
Full Text: View/download PDF

33. Improper choosability of graphs and maximum average degree

Author: Frédéric Havet and Jean-Sébastien Sereni
Subjects: 010201 computation theory & mathematics, 010102 general mathematics, Discrete Mathematics and Combinatorics, 0102 computer and information sciences, Geometry and Topology, 0101 mathematics, 01 natural sciences
Published: 2006
Full Text: View/download PDF

34. Finding a subdivision of a digraph

Author: Frédéric Havet, A. Karolinna Maia, Jørgen Bang-Jensen, Department of Mathematics and Computer Science [Odense] (IMADA), University of Southern Denmark (SDU), 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 (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), ANR-09-BLAN-0159,AGAPE,Algorithmes de graphes parametres et exacts(2009), Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: Discrete mathematics, Polynomial, General Computer Science, business.industry, 010102 general mathematics, Digraph, 0102 computer and information sciences, Directed graph, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 16. Peace & justice, Mathematical proof, 01 natural sciences, Theoretical Computer Science, Combinatorics, 010201 computation theory & mathematics, 0101 mathematics, business, Subdivision, Mathematics
Abstract: International audience; We consider the following problem for oriented graphs and digraphs: Given a directed graph D, does it contain a subdivision of a prescribed digraph F? We give a number of examples of polynomial instances, several NP-completeness proofs as well as a number of conjectures and open problems.
Published: 2015
Full Text: View/download PDF

35. Planar graphs with maximum degree Δ≥9 are (Δ+1)-edge-choosable—A short proof

Author: Frédéric Havet and Nathann Cohen
Subjects: Discrete mathematics, Degree (graph theory), 010102 general mathematics, 0102 computer and information sciences, Edge (geometry), 01 natural sciences, Theoretical Computer Science, Planar graph, Combinatorics, symbols.namesake, 010201 computation theory & mathematics, symbols, Discrete Mathematics and Combinatorics, 0101 mathematics, Mathematics
Abstract: We give a short proof of the following theorem due to Borodin (1990) [2]. Every planar graph G with maximum degree at least 9 is (@D(G)+1)-edge-choosable.
Published: 2010
Full Text: View/download PDF

36. (Circular) backbone colouring: forest backbones in planar graphs

Author: Ioan Todinca, Mathieu Liedloff, Frédéric Havet, Andrew D. King, 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 (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Department of Mathematics [Burnaby] (SFU), Simon Fraser University (SFU.ca), Department of computer science [Burnaby], Laboratoire d'Informatique Fondamentale d'Orléans (LIFO), Ecole Nationale Supérieure d'Ingénieurs de Bourges-Université d'Orléans (UO), Université d'Orléans (UO)-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and Université d'Orléans (UO)-Ecole Nationale Supérieure d'Ingénieurs de Bourges
Subjects: Discrete mathematics, Vertex (graph theory), Spanning tree, Applied Mathematics, 010102 general mathematics, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Galaxy, Planar graph, Combinatorics, symbols.namesake, Planar, 010201 computation theory & mathematics, symbols, Discrete Mathematics and Combinatorics, Chromatic scale, 0101 mathematics, NP-complete, Undirected graph, Mathematics
Abstract: International audience; Consider an undirected graph $G$ and a subgraph $H$ of $G$, on the same vertex set. The {\it $q$-backbone chromatic number} $\BBC_q(G,H)$ is the minimum $k$ such that $G$ can be properly coloured with colours from $\{1, \dots, k\}$, and moreover for each edge of $H$, the colours of its ends differ by at least $q$. In this paper we focus on the case when $G$ is planar and $H$ is a forest. We give a series of NP-hardness results as well as upper bounds for $\BBC_q(G,H)$, depending on the type of the forest (matching, galaxy, spanning tree). Eventually, we discuss a circular version of the problem.
Published: 2014
Full Text: View/download PDF

37. On the Grundy and b-chromatic numbers of a graph

Author: Frédéric Havet, Leonardo Sampaio, 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 (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: Discrete mathematics, General Computer Science, Applied Mathematics, 010102 general mathematics, Greedy Colouring, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Computer Science Applications, Vertex (geometry), NP-completeness, Combinatorics, 010201 computation theory & mathematics, Grundy number, Fixed Parameter Complexity, Bipartite graph, Online Colouring, Chromatic scale, 0101 mathematics, Greedy algorithm, Colouring, Mathematics
Abstract: The Grundy number of a graph G, denoted by Γ(G), is the largest k such that G has a greedy k-colouring, that is a colouring with k colours obtained by applying the greedy algorithm according to some ordering of the vertexes of G. The b-chromatic number of a graph G, denoted by χ b (G), is the largest k such that G has a b-colouring with k colours, that is a colouring in which each colour class contains a b-vertex, a vertex with neighbours in all other colour classes. Trivially χ b (G),Γ(G)≤Δ(G)+1. In this paper, we show that deciding if Γ(G)≤Δ(G) is NP-complete even for a bipartite graph G. We then show that deciding if Γ(G)≥|V(G)|−k or if χ b (G)≥|V(G)|−k are fixed parameter tractable problems with respect to the parameter k.
Published: 2013

38. The game Grundy number of graphs

Author: Xuding Zhu, Frédéric Havet, 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 (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Department of Mathematics [Jinhua], Zhejiang Normal University, Université Nice Sophia Antipolis (... - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS)
Subjects: Control and Optimization, Applied Mathematics, Nim, 010102 general mathematics, 0102 computer and information sciences, trees, game Grundy number, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Computer Science Applications, Vertex (geometry), Combinatorics, Computational Theory and Mathematics, Alice and Bob, 010201 computation theory & mathematics, Grundy number, Theory of computation, Grundy's game, Colouring game, Discrete Mathematics and Combinatorics, 0101 mathematics, Game tree, partial 2-trees, Mathematics
Abstract: International audience; Given a graph G = (V;E), two players, Alice and Bob, alternate their turns in choosing uncoloured vertices to be coloured. Whenever an uncoloured vertex is chosen, it is coloured by the least positive integer not used by any of its coloured neighbours. Alice's goal is to minimize the total number of colours used in the game, and Bob's goal is to maximize it. The game Grundy number of G is the number of colours used in the game when both players use optimal strategies. It is proved in this paper that the maximum game Grundy number of forests is 3, and the game Grundy number of any partial 2-tree is at most 7.
Published: 2013
Full Text: View/download PDF

39. Backbone colouring: Tree backbones with small diameter in planar graphs

Author: Ana Silva, Rudini Menezes Sampaio, Frédéric Havet, Victor Campos, Parallelism, Graphs and Optimization Research Group (ParGO), Universidade Federal do Ceará = Federal University of Ceará (UFC), 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 (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Université Nice Sophia Antipolis (... - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS)
Subjects: Discrete mathematics, Small diameter, Spanning tree, Conjecture, General Computer Science, Spanning subgraph, Shortest-path tree, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Theoretical Computer Science, Planar graph, Combinatorics, symbols.namesake, 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, symbols, Mathematics
Abstract: Given a graph G and a spanning subgraph T of G , a backbone k -colouring for ( G , T ) is a mapping c : V ( G ) → { 1 , … , k } such that | c ( u ) − c ( v ) | ≥ 2 for every edge u v ∈ E ( T ) and | c ( u ) − c ( v ) | ≥ 1 for every edge u v ∈ E ( G ) ∖ E ( T ) . The backbone chromatic number B B C ( G , T ) is the smallest integer k such that there exists a backbone k -colouring of ( G , T ) . In 2007, Broersma et al. [2] conjectured that B B C ( G , T ) ≤ 6 for every planar graph G and every spanning tree T of G . In this paper, we prove this conjecture when T has diameter at most four.
Published: 2013
Full Text: View/download PDF

40. Oriented trees in digraphs

Author: Cláudia Linhares Sales, Louigi Addario-Berry, Stéphan Thomassé, Frédéric Havet, Bruce Reed, Department of Mathematics and Statistics [Montréal], McGill University = Université McGill [Montréal, Canada], 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 (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Parallelism, Graphs and Optimization Research Group (ParGO), Universidade Federal do Ceará = Federal University of Ceará (UFC), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: Discrete mathematics, Conjecture, 010102 general mathematics, Digraph, 0102 computer and information sciences, Function (mathematics), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Theoretical Computer Science, Combinatorics, Integer, 010201 computation theory & mathematics, Discrete Mathematics and Combinatorics, Order (group theory), Tree (set theory), 0101 mathematics, Mathematics
Abstract: Let f ( k ) be the smallest integer such that every f ( k ) -chromatic digraph contains every oriented tree of order k . Burr proved f ( k ) ≤ ( k − 1 ) 2 in general, and he conjectured f ( k ) = 2 k − 2 . Burr also proved that every ( 8 k − 7 ) -chromatic digraph contains every antidirected tree. We improve both of Burr’s bounds. We show that f ( k ) ≤ k 2 / 2 − k / 2 + 1 and that every antidirected tree of order k is contained in every ( 5 k − 9 ) -chromatic digraph. We make a conjecture that explains why antidirected trees are easier to handle. It states that if | E ( D ) | > ( k − 2 ) | V ( D ) | , then the digraph D contains every antidirected tree of order k . This is a common strengthening of both Burr’s conjecture for antidirected trees and the celebrated Erdős-Sos Conjecture. The analogue of our conjecture for general trees is false, no matter what function f ( k ) is used in place of k − 2 . We prove our conjecture for antidirected trees of diameter 3 and present some other evidence for it. Along the way, we show that every acyclic k -chromatic digraph contains every oriented tree of order k and suggest a number of approaches for making further progress on Burr’s conjecture.
Published: 2013
Full Text: View/download PDF

41. On the (non-)existence of polynomial kernels for $P_l$-free edge modification problems

Author: Christophe Paul, Sylvain Guillemot, Frédéric Havet, Anthony Perez, Méthodes et Algorithmes pour la Bioinformatique (MAB), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), 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 (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique Fondamentale d'Orléans (LIFO), Ecole Nationale Supérieure d'Ingénieurs de Bourges-Université d'Orléans (UO), ANR-09-BLAN-0159,AGAPE,Algorithmes de graphes parametres et exacts(2009), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and Université d'Orléans (UO)-Ecole Nationale Supérieure d'Ingénieurs de Bourges
Subjects: Vertex (graph theory), Discrete mathematics, General Computer Science, Applied Mathematics, Parameterized complexity, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Quotient graph, Computer Science Applications, Modular decomposition, Combinatorics, 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Cograph, Hereditary property, Graph property, Time complexity, Mathematics
Abstract: Given a graph G=(V,E) and a positive integer k, an edge modification problem for a graph property ź consists in deciding whether there exists a set F of pairs of V of size at most k such that the graph $H=(V,E\vartriangle F)$ satisfies the property ź. In the źedge-completion problem, the set F is constrained to be disjoint from E; in the źedge-deletion problem, F is a subset of E; no constraint is imposed on F in the źedge-editing problem. A number of optimization problems can be expressed in terms of graph modification problems which have been extensively studied in the context of parameterized complexity (Cai in Inf. Process. Lett. 58:171---176, 1996; Fellows et al. in FCT, pp. 312---321, 2007; Heggernes et al. in STOC, pp. 374---381, 2007). When parameterized by the size k of the set F, it has been proved that if ź is a hereditary property characterized by a finite set of forbidden induced subgraphs, then the three ź edge-modification problems are FPT (Cai in Inf. Process. Lett. 58:171---176, 1996). It was then natural to ask (Bodlaender et al. in IWPEC, 2006) whether these problems also admit a polynomial kernel. in polynomial time to an equivalent instance (Gź,kź) with size bounded by a polynomial in k). Using recent lower bound techniques, Kratsch and Wahlstrom answered this question negatively (Kratsch and Wahlstrom in IWPEC, pp. 264---275, 2009). However, the problem remains open on many natural graph classes characterized by forbidden induced subgraphs. question to characterize for which type of graph properties, the parameterized edge-modification problems have polynomial kernels. Kratsch and Wahlstrom asked whether the result holds when the forbidden subgraphs are paths or cycles and pointed out that the problem is already open in the case of P4-free graphs (i.e. cographs). This paper provides positive and negative results in that line of research. We prove that Parameterized cograph edge-modification problems have cubic vertex kernels whereas polynomial kernels are unlikely to exist for the Pl-free edge-deletion and the Cl-free edge-deletion problems for lź7 and lź4 respectively. Indeed, if they exist, then NP⊆coNP/poly.
Published: 2013
Full Text: View/download PDF

42. Enumerating the edge-colourings and total colourings of a regular graph

Author: Frédéric Havet, Stéphane Bessy, Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), 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 (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), ANR, Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), INRIA, and Bessy, Stéphane
Subjects: Factor-critical graph, Control and Optimization, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0211 other engineering and technologies, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Distance-regular graph, Combinatorics, Graph power, Discrete Mathematics and Combinatorics, Mathematics, Discrete mathematics, 021103 operations research, Applied Mathematics, Voltage graph, Quartic graph, Computer Science Applications, Computational Theory and Mathematics, 010201 computation theory & mathematics, Cubic graph, Regular graph, Tutte polynomial, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: International audience; In this paper, we are interested in computing the number of edge colourings and total colourings of a connected graph. We prove that the maximum number of $k$-edge-colourings of a connected $k$-regular graph on $n$ vertices is $k\cdot((k-1)!)^{n/2}$. Our proof is constructive and leads to a branching algorithm enumerating all the $k$-edge-colourings of a connected $k$-regular graph in time $O^*(((k-1)!)^{n/2})$ and polynomial space. In particular, we obtain a algorithm to enumerate all the $3$-edge-colourings of a connected cubic graph in time $O^*(2^{n/2})=O^*(1.4143^n)$ and polynomial space. This improves the running time of $O^*(1.5423^n)$ of the algorithm due to Golovach et al.~\cite{GKC10}. We also show that the number of $4$-total-colourings of a connected cubic graph is at most $3\cdot 2^{3n/2}$. Again, our proof yields a branching algorithm to enumerate all the $4$-total-colourings of a connected cubic graph.
Published: 2012
Full Text: View/download PDF

43. On Spanning Galaxies in Digraphs

Author: Frédéric Havet, Daniel Gonçalves, Stéphan Thomassé, Alexandre Pinlou, Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), 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 (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), ANR-09-BLAN-0159,AGAPE,Algorithmes de graphes parametres et exacts(2009), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), and École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: Arborescence, Parameterized complexity, 0102 computer and information sciences, Astrophysics::Cosmology and Extragalactic Astrophysics, Star (graph theory), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Combinatorics, Computer Science::Discrete Mathematics, Discrete Mathematics and Combinatorics, 0101 mathematics, Computer Science::Data Structures and Algorithms, Astrophysics::Galaxy Astrophysics, Mathematics, Minimum degree spanning tree, Discrete mathematics, Mathematics::Combinatorics, Applied Mathematics, Arboricity, 010102 general mathematics, Spanning galaxy, Digraph, Directed graph, Directed star arboricity, Galaxy, Even strong subdigraph, 010201 computation theory & mathematics, Fixed parameter tractable, Algorithms
Abstract: In a directed graph, a star is an arborescence with at least one arc, in which the root dominates all the other vertices. A galaxy is a vertex-disjoint union of stars. In this paper, we consider the Spanning Galaxy problem of deciding whether a digraph D has a spanning galaxy or not. We show that although this problem is NP-complete (even when restricted to acyclic digraphs), it becomes polynomial-time solvable when restricted to strong digraphs. In fact, we prove that restricted to this class, the Spanning Galaxy problem is equivalent to the problem of deciding whether a strong digraph has a strong subdigraph with an even number of vertices. We then show a polynomial-time algorithm to solve this problem. We also consider some parameterized version of the Spanning Galaxy problem. Finally, we improve some results concerning the notion of directed star arboricity of a digraph D, which is the minimum number of galaxies needed to cover all the arcs of D. We show in particular that dst(D)@[email protected](D)+1 for every digraph D and that dst(D)@[email protected](D) for every acyclic digraph D.
Published: 2012
Full Text: View/download PDF

44. Griggs and Yeh's Conjecture and L(p,1)-labelings

Author: Bruce Reed, Jean-Sébastien Sereni, Frédéric Havet, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), 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 (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: Discrete mathematics, Graph labeling, Conjecture, generalized coloring, ACM: G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.2: Graph Theory/G.2.2.1: Graph labeling, General Mathematics, 010102 general mathematics, graph labeling, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Vertex (geometry), Combinatorics, ACM: G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.2: Graph Theory, Integer, 010201 computation theory & mathematics, channel assignment, graph coloring, Graph coloring, 0101 mathematics, Mathematics
Abstract: An $L(p,1)$-labeling of a graph is a function $f$ from the vertex set to the positive integers such that $|f(x)-f(y)|\geqslant p$ if dist$(x,y)=1$ and $|f(x)-f(y)|\geqslant 1$ if dist$(x,y)=2$, where dist$(x,y)$ is the distance between the two vertices $x$ and $y$ in the graph. The span of an $L(p,1)$-labeling $f$ is the difference between the largest and the smallest labels used by $f$. In 1992, Griggs and Yeh conjectured that every graph with maximum degree $\Delta\geqslant 2$ has an $L(2,1)$-labeling with span at most $\Delta^2$. We settle this conjecture for $\Delta$ sufficiently large. More generally, we show that for any positive integer $p$ there exists a constant $\Delta_p$ such that every graph with maximum degree $\Delta\geqslant \Delta_p$ has an $L(p,1)$-labeling with span at most $\Delta^2$. This yields that for each positive integer $p$, there is an integer $C_p$ such that every graph with maximum degree $\Delta$ has an $L(p,1)$-labeling with span at most $\Delta^2+C_p$.
Published: 2012
Full Text: View/download PDF

45. Weighted Improper Colouring

Author: Jean-Claude Bermond, Remigiusz Modrzejewski, Júlio Araújo, Frédéric Havet, Frédéric Giroire, Dorian Mazauric, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), 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 (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Parallelism, Graphs and Optimization Research Group (ParGO), Universidade Federal do Ceará = Federal University of Ceará (UFC), This work was partially supported by r'egion PACA and ANR International Taiwan GRATEL (ANR-09-BLAN-0373)., ANR-09-BLAN-0159,AGAPE,Algorithmes de graphes parametres et exacts(2009), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), Models for the performance analysis and the control of networks (MAESTRO), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), région PACA, and INRIA
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Weight function, Heuristic (computer science), Frequency assignment, Graph colouring, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Partition problem, interference, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Interference (wave propagation), 01 natural sciences, Square (algebra), radio networks, Theoretical Computer Science, Combinatorics, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Integer, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, Chromatic scale, Integer programming, Mathematics, Discrete mathematics, graph colouring, Wireless network, Hexagonal crystal system, 020206 networking & telecommunications, Frequency assignment problem, Graph, Computational Theory and Mathematics, 010201 computation theory & mathematics, frequency assignment, Node (circuits), Voronoi diagram, improper colouring
Abstract: In this paper, we study a colouring problem motivated by a practical frequency assignment problem and, up to our best knowledge, new. In wireless networks, a node interferes with other nodes, the level of interference depending on numerous parameters: distance between the nodes, geographical topography, obstacles, etc. We model this with a weighted graph $(G,w)$ where the weight function $w$ on the edges of $G$ represents the noise (interference) between the two end-vertices. The total interference in a node is then the sum of all the noises of the nodes emitting on the same frequency. A weighted $t$-improper $k$-colouring of $(G,w)$ is a $k$-colouring of the nodes of $G$ (assignment of $k$ frequencies) such that the interference at each node does not exceed the threshold $t$. We consider here the Weighted Improper Colouring problem which consists in determining the weighted $t$-improper chromatic number defined as the minimum integer $k$ such that $(G,w)$ admits a weighted $t$-improper $k$-colouring. We also consider the dual problem, denoted the Threshold Improper Colouring problem, where, given a number $k$ of colours, we want to determine the minimum real $t$ such that $(G,w)$ admits a weighted $t$-improper $k$-colouring. We first present general upper bounds for both problems; in particular we show a generalisation of Lovász's Theorem for the weighted $t$-improper chromatic number. We then show how to transform an instance of the Threshold Improper Colouring problem into another equivalent one where the weights are either one or $M$, for a sufficiently large $M$. Motivated by the original application, we then study a special interference model on various grids (square, triangular, hexagonal) where a node produces a noise of intensity 1 for its neighbours and a noise of intensity 1/2 for the nodes at distance two. We derive the weighted $t$-improper chromatic number for all values of $t$. Finally, we model the problem using integer linear programming, propose and test heuristic and exact Branch-and-Bound algorithms on random cell-like graphs, namely the Poisson-Voronoi tessellations.; Dans ce papier, nous étudions un nouveau problème de coloration motivé par un problème pratique d'allocation de fréquences. Dans les réseaux sans-fil, un n\oe{}ud interfère avec d'autres, à un niveau dépendant de nombreux paramètres : la distance entre les n\oe{}uds, la topographie physique, les obstacles, etc. Nous modélisons cela par un graphe arête-valué $(G,w)$ oú le poids d'une arête représente le bruit (ou l'interférence) entre ces deux extrémités. L'interférence totale au niveau d'un n\oe{}ud est alors la somme de tous les bruits entre ce n\oe{}ud et les autres n\oe{}uds émettant avec la même fréquence. Une $k$-coloration $t$-impropre pondérée de $(G,w)$ est une $k$-coloration des n\oe{}uds de $G$ (assignation de $k$ fréquences) telle que l'interférence à chaque n\oe{}ud n'excède pas un certain seuil $t$. Dans ce papier, nous étudions le problème de la coloration impropre pondérée qui consiste à déterminer le nombre chromatique $t$-impropre pondéré d'un graphe arête-valué $(G,w)$, qui est le plus petit entier $k$ tel que $(G,w)$ admette une $k$-coloration $t$-impropre pondérée. Nous considérons également le problème Threshold Improper Colouring (le problème dual) qui, étant donné un nombre de couleurs (fréquences), consiste à déterminer le plus petit réel $t$ tel que $(G,w)$ admette une $k$-coloration $t$-impropre pondérée. Nous montrons d'abord des bornes supérieures générales; en particulier nous prouvons une généralisation du théorème de Lovász pour le problème du nombre chromatique $t$-impropre pondéré. Nous montrons ensuite comment transformer une instance du probléme Threshold Improper Colouring en une instance équivalente avec des poids $1$ ou $M$, pour une valeur de $M$ suffisamment grande. Motivé par l'origine du problème, nous étudions un modèle d'interférence particulier pour différentes grilles (carrée, triangulaire, hexagonale) oú un n\oe{}ud produit un bruit d'intensité $1$ pour ses voisins et un bruit d'intensité $1/2$ pour les n\oe{}uds à distance deux. Nous montrons le nombre chromatique $t$-impropre pour toutes les valeurs de $t$. Enfin, nous modélisons le problème par des programmes linéaires en nombres entiers, nous proposons des heuristiques et des algorithmes exactes d'énumération par la technique du Branch-and-Bound. Nous les testons pour des graphes aléatoires ressemblant à des réseaux cellulaires, à savoir des tessellations de Poisson-Voronoi.
Published: 2011
Full Text: View/download PDF

46. Exact Algorithms for L(2,1)-Labeling of Graphs

Author: Martin Klazar, Mathieu Liedloff, Jan Kratochvíl, Frédéric Havet, Dieter Kratsch, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), 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 (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Laboratoire d'Informatique Théorique et Appliquée (LITA), Université de Lorraine (UL), Laboratoire d'Informatique Fondamentale d'Orléans (LIFO), Ecole Nationale Supérieure d'Ingénieurs de Bourges-Université d'Orléans (UO), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and Université d'Orléans (UO)-Ecole Nationale Supérieure d'Ingénieurs de Bourges
Subjects: Vertex (graph theory), Discrete mathematics, 021103 operations research, General Computer Science, Applied Mathematics, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0211 other engineering and technologies, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Graph, Computer Science Applications, Exponential function, Running time, Combinatorics, Dynamic programming, Exact algorithm, 010201 computation theory & mathematics, Common neighbor, Theory of computation, Algorithm, Mathematics
Abstract: International audience; The notion of distance constrained graph labelings, motivated by the Frequency Assignment Problem, reads as follows: A mapping from the vertex set of a graph $G=(V,E)$ into an interval of integers $\{0, \dots ,k\}$ is an $L(2,1)$-labeling of $G$ of span $k$ if any two adjacent vertices are mapped onto integers that are at least 2 apart, and every two vertices with a common neighbor are mapped onto distinct integers. It is known that for any fixed $k\ge 4$, deciding the existence of such a labeling is an NP-complete problem. We present exact exponential time algorithms that are faster than the naive $O^*((k+1)^n)$ algorithm that would try all possible mappings. The improvement is best seen in the first NP-complete case of $k=4$, where the running time of our algorithm is $O(1.3006^n)$. Furthermore we show that dynamic programming can be used to establish an $O(3.8730^n)$ algorithm to compute an optimal $L(2,1)$-labeling.
Published: 2011
Full Text: View/download PDF

47. Linear and 2-Frugal Choosability of Graphs of Small Maximum Average Degree

Author: Frédéric Havet, Nathann Cohen, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), 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 (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Université Nice Sophia Antipolis (... - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS)
Subjects: Discrete mathematics, Degree (graph theory), 010102 general mathematics, Discharging method, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Theoretical Computer Science, Vertex (geometry), Planar graph, Combinatorics, symbols.namesake, 010201 computation theory & mathematics, symbols, Discrete Mathematics and Combinatorics, 0101 mathematics, Mathematics
Abstract: A proper vertex colouring of a graph G is 2-frugal (resp. linear) if the graph induced by the vertices of any two colour classes is of maximum degree 2 (resp. is a forest of paths). A graph G is 2-frugally (resp. linearly) L-colourable if for a given list assignment $${L:V(G)\mapsto 2^{\mathbb N}}$$, there exists a 2-frugal (resp. linear) colouring c of G such that $${c(v) \in L(v)}$$ for all $${v\in V(G)}$$. If G is 2-frugally (resp. linearly) L-list colourable for any list assignment such that |L(v)| ≥ k for all $${v\in V(G)}$$, then G is 2-frugally (resp. linearly) k-choosable. In this paper, we improve some bounds on the 2-frugal choosability and linear choosability of graphs with small maximum average degree.
Published: 2011

48. 5-colouring graphs with 4 crossings

Author: Rok Erman, Ondřej Pangrác, Bernard Lidický, Frédéric Havet, Departement of Mathematics [Slovenia], University of Ljubljana, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), 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 (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Institute for Theoretical Computer Science (ITI), Charles University [Prague] (CU), Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, ANR-09-BLAN-0159,AGAPE,Algorithmes de graphes parametres et exacts(2009), Université Nice Sophia Antipolis (... - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS)
Subjects: Discrete mathematics, Block graph, Clique-sum, General Mathematics, 010102 general mathematics, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Clique graph, 01 natural sciences, 1-planar graph, Simplex graph, Treewidth, Combinatorics, 010201 computation theory & mathematics, Split graph, Crossing number (graph theory), 0101 mathematics, Mathematics
Abstract: International audience; We answer in the negative a question of Oporowski and Zhao [Discrete Math., 309 (2009), pp. 2948-2951] asking whether every graph with crossing number at most 5 and clique number at most 5 is 5-colorable. However, we show that every graph with crossing number at most 4 and clique number at most 5 is 5-colorable. We also show some colorability results on graphs that can be made planar by removing a few edges. In particular, we show that, if a graph with clique number at most 5 has three edges whose removal leaves the graph planar, then it is 5-colorable.
Published: 2011
Full Text: View/download PDF

49. Improper colouring of weighted grid and hexagonal graphs

Author: Cláudia Linhares Sales, Florian Huc, Frédéric Havet, Jean-Claude Bermond, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), 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 (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Centre Universitaire d'Informatique, Université de Genève (UNIGE), Laboratórios de PesquIsa em ComputAção (LIA), Universidade Federal do Ceará = Federal University of Ceará (UFC), ANR-09-BLAN-0373,GraTel(2009), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and Université de Genève = University of Geneva (UNIGE)
Subjects: Discrete mathematics, 021103 operations research, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0211 other engineering and technologies, Approximation algorithm, 0102 computer and information sciences, 02 engineering and technology, Complete coloring, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Brooks' theorem, Greedy coloring, Combinatorics, Edge coloring, 010201 computation theory & mathematics, Discrete Mathematics and Combinatorics, Graph coloring, Fractional coloring, Mathematics, List coloring
Abstract: International audience; We study a weighted improper colouring problem motivated by a frequency allocation problem. It consists of associating to each vertex a set of p(v) (weight) distinct colours (frequencies), such that the set of vertices having a given colour induces a graph of degree at most k (the case k = 0 corresponds to a proper coloring). The objective is to minimize the number of colors. We propose approximation algorithms to compute such colouring for general graphs. We apply these to obtain good approximation ratio for grid and hexagonal graphs. Furthermore we give exact results for the 2-dimensional grid and the triangular lattice when the weights are all the same.
Published: 2010
Full Text: View/download PDF

50. On the Grundy Number of a Graph

Author: Leonardo Sampaio, Frédéric Havet, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), 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 (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), CAPES/Brazil ANR Blanc AGAPE, ANR-09-BLAN-0159,AGAPE,Algorithmes de graphes parametres et exacts(2009), Université Nice Sophia Antipolis (... - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS)
Subjects: Discrete mathematics, 021103 operations research, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0211 other engineering and technologies, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Graph, Combinatorics, 010201 computation theory & mathematics, Grundy number, Bound graph, Greedy algorithm, Mathematics
Abstract: The Grundy number of a graph G, denoted by ${\it \Gamma} (G)$, is the largest k such that G has a greedy k-colouring, that is a colouring with k colours obtained by applying the greedy algorithm according to some ordering of the vertices of G. Trivially ${\it \Gamma(G)\leq \Delta(G)+1}$. In this paper, we show that deciding if ${\it \Gamma(G)\leq \Delta(G)}$ is NP-complete. We then show that deciding if ${\it \Gamma(G)\geq \mid V(G)\mid-k}$ is fixed parameter tractable with respect to the parameter k.
Published: 2010
Full Text: View/download PDF

Catalog

Books, media, physical & digital resources

See catalog results

Searchworks

Select search scope, currently: Articles Catalog books, media & more in Jio Institute collections Articles journal articles & other e-resources

Search

Search Constraints

Refine your results

Search Limiters

Topic

Publication Year Range

Language

Journal

Database

Publisher

58 results on '"Frédéric Havet"'

Search Results

Catalog

Select search scope, currently: Articles

Catalog

books, media & more in Jio Institute collections

Articles

journal articles & other e-resources