Search

Your search keyword '"Effantin, Brice"' showing total 82 results
Start Over Author "Effantin, Brice"
82 results on '"Effantin, Brice"'

1. Incidence, a Scoring Positional Game on Graphs

Author

Bagan, Guillaume, Deschamps, Quentin, Duchêne, Eric, Durain, Bastien, Effantin, Brice, Gledel, Valentin, Oijid, Nacim, and Parreau, Aline

Subjects
Mathematics - Combinatorics
Abstract

Positional games have been introduced by Hales and Jewett in 1963 and have been extensively investigated in the literature since then. These games are played on a hypergraph where two players alternately select an unclaimed vertex of it. In the Maker-Breaker convention, if Maker manages to fully take a hyperedge, she wins, otherwise, Breaker is the winner. In the Maker-Maker convention, the first player to take a hyperedge wins. In both cases, the game stops as soon as Maker has taken a hyperedge. By definition, this family of games does not handle scores and cannot represent games in which players want to maximize a quantity. In this work, we introduce scoring positional games, that consist in playing on a hypergraph until all the vertices are claimed, and by defining the score as the number of hyperedges a player has fully taken. We focus here on Incidence, a scoring positional game played on a 2-uniform hypergraph, i.e. an undirected graph. In this game, two players alternately claim the vertices of a graph and score the number of edges for which they own both end vertices. In the Maker-Breaker version, Maker aims at maximizing the number of edges she owns, while Breaker aims at minimizing it. In the Maker-Maker version, both players try to take more edges than their opponent. We first give some general results on scoring positional games such that their membership in Milnor's universe and some general bounds on the score. We prove that, surprisingly, computing the score in the Maker-Breaker version of Incidence is PSPACE-complete whereas in the Maker-Maker convention, the relative score can be obtained in polynomial time. In addition, for the Maker-Breaker convention, we give a formula for the score on paths by using some equivalences due to Milnor's universe. This result implies that the score on cycles can also be computed in polynomial time.

Published
2022

3. A characterization of b-chromatic and partial Grundy numbers by induced subgraphs

Author

Effantin, Brice, Gastineau, Nicolas, and Togni, Olivier

Subjects
Computer Science - Discrete Mathematics
Abstract

Gy{\'a}rf{\'a}s et al. and Zaker have proven that the Grundy number of a graph $G$ satisfies $\Gamma(G)\ge t$ if and only if $G$ contains an induced subgraph called a $t$-atom.The family of $t$-atoms has bounded order and contains a finite number of graphs.In this article, we introduce equivalents of $t$-atoms for b-coloring and partial Grundy coloring.This concept is used to prove that determining if $\varphi(G)\ge t$ and $\partial\Gamma(G)\ge t$ (under conditions for the b-coloring), for a graph $G$, is in XP with parameter $t$.We illustrate the utility of the concept of $t$-atoms by giving results on b-critical vertices and edges, on b-perfect graphs and on graphs of girth at least $7$.

Published
2015

4. Search and Aggregation in XML Documents

Author

Habi, Abdelmalek, Effantin, Brice, Kheddouci, Hamamache, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Benslimane, Djamal, editor, Damiani, Ernesto, editor, Grosky, William I., editor, Hameurlain, Abdelkader, editor, Sheth, Amit, editor, and Wagner, Roland R., editor

Published
2017
Full Text
View/download PDF

6. Incidence, a scoring positional game on graphs

Author

Bagan, Guillaume, primary, Deschamps, Quentin, additional, Duchêne, Eric, additional, Durain, Bastien, additional, Effantin, Brice, additional, Gledel, Valentin, additional, Oijid, Nacim, additional, and Parreau, Aline, additional

Published
2023
Full Text
View/download PDF

7. Incidence, a scoring positional game on graphs

Author

Bagan, Guillaume, Deschamps, Quentin, Duchêne, Eric, Durain, Bastien, Effantin, Brice, Gledel, Valentin, Oijid, Nacim, Parreau, Aline, Bagan, Guillaume, Deschamps, Quentin, Duchêne, Eric, Durain, Bastien, Effantin, Brice, Gledel, Valentin, Oijid, Nacim, and Parreau, Aline

Abstract

Positional games have been introduced by Hales and Jewett in 1963 and have been extensively investigated in the literature since then. These games are played on a hypergraph where two players alternately select an unclaimed vertex of it. In the Maker-Breaker convention, if Maker manages to fully take a hyperedge, she wins, otherwise, Breaker is the winner. In the Maker-Maker convention, the first player to take a hyperedge wins, and if no one manages to do it, the game ends by a draw. In both cases, the game stops as soon as Maker has taken a hyperedge. By definition, this family of games does not handle scores and cannot represent games in which players want to maximize a quantity. In this work, we introduce scoring positional games, that consist in playing on a hypergraph until all the vertices are claimed, and by defining the score as the number of hyperedges a player has fully taken. We focus here on INCIDENCE, a scoring positional game played on a 2-uniform hypergraph, i.e. an undirected graph. In this game, two players alternately claim the vertices of a graph and score the number of edges for which they own both end vertices. In the Maker-Breaker version, Maker aims at maximizing the number of edges she owns, while Breaker aims at minimizing it. In the Maker-Maker version, both players try to take more edges than their opponent. We first give some general results on scoring positional games such that their membership in Milnor's universe and some general bounds on the score. We prove that, surprisingly, computing the score in the Maker-Breaker version of INCIDENCE is PSPACE-complete whereas in the Maker-Maker convention, the relative score can be obtained in polynomial time. In addition, for the Maker-Breaker convention, we give a formula for the score on paths by using some equivalences due to Milnor's universe. This result implies that the score on cycles can also be computed in polynomial time.

Published
2023
Full Text
View/download PDF

9. A Graph Enrichment Based Clustering over Vertically Partitioned Data

Author

Benabdeslem, Khalid, Effantin, Brice, Elghazel, Haytham, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Goebel, Randy, editor, Siekmann, Jörg, editor, Wahlster, Wolfgang, editor, Tang, Jie, editor, King, Irwin, editor, Chen, Ling, editor, and Wang, Jianyong, editor

Published
2011
Full Text
View/download PDF

10. A Self-stabilizing Algorithm for the Minimum Color Sum of a Graph

Author

Sun, Huang, Effantin, Brice, Kheddouci, Hamamache, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Rao, Shrisha, editor, Chatterjee, Mainak, editor, Jayanti, Prasad, editor, Murthy, C. Siva Ram, editor, and Saha, Sanjoy Kumar, editor

Published
2008
Full Text
View/download PDF

11. An Incremental Distributed Algorithm for a Partial Grundy Coloring of Graphs

Author

Dekar, Lyes, Effantin, Brice, Kheddouci, Hamamache, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Stojmenovic, Ivan, editor, Thulasiram, Ruppa K., editor, Yang, Laurence T., editor, Jia, Weijia, editor, Guo, Minyi, editor, and de Mello, Rodrigo Fernandes, editor

Published
2007
Full Text
View/download PDF

12. A Distributed Algorithm for a b-Coloring of a Graph

Author

Effantin, Brice, Kheddouci, Hamamache, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Guo, Minyi, editor, Yang, Laurence T., editor, Di Martino, Beniamino, editor, Zima, Hans P., editor, Dongarra, Jack, editor, and Tang, Feilong, editor

Published
2006
Full Text
View/download PDF

13. Generation of Unordered Binary Trees

Author

Effantin, Brice, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Laganá, Antonio, editor, Gavrilova, Marina L., editor, Kumar, Vipin, editor, Mun, Youngsong, editor, Tan, C. J. Kenneth, editor, and Gervasi, Osvaldo, editor

Published
2004
Full Text
View/download PDF

19. On the game coloring index of F+-decomposable graphs

Author

Charpentier, Clément, Effantin, Brice, Paris, Gabrielle, Institut Fourier (IF ), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Graphes, AlgOrithmes et AppLications (GOAL), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), 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é 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), Effantin, Brice, Institut Fourier (IF), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA), 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-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
[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2018

22. A note on Grundy colorings of central graphs

Author

Effantin, Brice, Effantin, Brice, Appel à projets générique - Jeux et graphes - - GAG2014 - ANR-14-CE25-0006 - Appel à projets générique - VALID, Graphes, AlgOrithmes et AppLications (GOAL), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), 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), and ANR-14-CE25-0006,GAG,Jeux et graphes(2014)

Subjects
[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], Mathematics::Combinatorics, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Grundy coloring, Central graph, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Vertex coloring, 2010 MSC: 05C15
Abstract

International audience; A Grundy coloring of a graph G is a proper vertex coloring of G where any vertex x, colored with c(x), has a neighbor of any color 1,2,...,c(x)-1. A central graph G^c is obtained from G by adding an edge between any two non adjacent vertices in G and subdividing any edge of G once. In this note we focus on Grundy colorings of central graphs. We present some bounds related to parameters of G and a Nordhaus-Gaddum inequality. We also determine exact values for the Grundy coloring of some central classical graphs.

Published
2017

25. On parameterized complexity to determine b-chromatic and partial Grundy numbers

Author

Gastineau, Nicolas, Togni, Olivier, Effantin, Brice, Graphes, Algorithmes et Multi-Agents (GrAMA), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), 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), Laboratoire d'Electronique, d'Informatique et d'Image [EA 7508] (Le2i), Université de Technologie de Belfort-Montbeliard (UTBM)-Université de Bourgogne (UB)-École Nationale Supérieure d'Arts et Métiers (ENSAM), Arts et Métiers Sciences et Technologies, HESAM Université (HESAM)-HESAM Université (HESAM)-Arts et Métiers Sciences et Technologies, HESAM Université (HESAM)-HESAM Université (HESAM)-AgroSup Dijon - Institut National Supérieur des Sciences Agronomiques, de l'Alimentation et de l'Environnement-Centre National de la Recherche Scientifique (CNRS), Graphes, AlgOrithmes et AppLications (GOAL), and Effantin, Brice

Subjects
[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2014

27. Distance edge coloring of the Kronecker product of some graphs

Author

Effantin, Brice, Kheddouci, Hamamache, Seba, Hamida, Graphes, AlgOrithmes et AppLications (GOAL), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), 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), and Université de Lyon-Université Lumière - Lyon 2 (UL2)

Subjects
[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
Abstract

International audience; Given a graph G = (V,E), an l-edge coloring of G is a function from the edges E to colors {1,2, · · · ,k} such that any two edges within distance l of each other are assigned different colors. In this paper, we determine bounds and exact values of k for the Kronecker product of two paths, two cycles, a path by a cycle, two stars and the graph K_2 by other graphs.

Published
2014

29. Distance edge coloring and collision-free communication in wireless sensor networks

Author

Drira, Kaouther, Seba, Hamida, Effantin, Brice, Kheddouci, Hamamache, Laboratoire d'Informatique pour l'Entreprise et les Systèmes de Production (LIESP), 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), Graphes, Algorithmes et Multi-Agents (GrAMA), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), 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), and Université de Lyon-Université Lumière - Lyon 2 (UL2)

Subjects
[INFO]Computer Science [cs], MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

International audience; Motivated by the problem of link scheduling in wireless sensor networks where differentsensors have different transmission and interference ranges and may be mobile, we study theproblem of distance edge coloring of graphs which is a generalization of proper edge coloring.Let G be a graph modeling a sensor network. An ℓ-distance edge coloring of G is a coloringof the edges of G such that any two edges within distance ℓ of each other are assigneddifferent colors. The parameter ℓ is chosen so that the links corresponding to two edges thatare assigned the same color do not interfere. We investigate the ℓ-distance edge coloringproblem on several families of graphs which can be used as topologies in sensor deployment.We focus on determining the minimum number of colors needed and on optimal coloringalgorithms.

Published
2013
Full Text
View/download PDF

30. GraphExploiter

Author

Lequay, Victor, primary, Ringot, Alexis, additional, Haddad, Mohammed, additional, Effantin, Brice, additional, and Kheddouci, Hamamache, additional

Published
2015
Full Text
View/download PDF

31. Distance-edge-coloring of power graphs

Author

Drira, Kaouther, Seba, Hamida, Effantin, Brice, Kheddouci, Hamamache, Laboratoire d'Informatique pour l'Entreprise et les Systèmes de Production (LIESP), 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), Graphes, AlgOrithmes et AppLications (GOAL), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), 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), and Equipe, Graphe Liesp

Subjects
TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Data_CODINGANDINFORMATIONTHEORY, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

International audience; The \ell-distance-edge-coloring is a generalization of the edge-coloring that tries to assign a color from 1 to k to each edge such that any two edges of distance at most \ell have distinct colors. The minimum number of colors used to color a graph with an \ell-distance-edge-coloring is called the \ell-chromatic index. Solving the \ell-distance-edge-coloring problem is different from determining the chromatic index, by Vizing's theorem, for its power graph. The \ell-distance-edge-coloring is thus an original problem which is NP-hard in general. We study the \ell-distance-edge-coloring problem in some classes of graphs in order to bring a new insight on the relative difficulties of this problem. We focus on the \ell-chromatic index for some classes of p-th power graphs. We present, for any integer \ell\geq0, the exact values for the \ell-chromatic index for power graphs of paths and complete k-ary trees, and bounds and exact values for the \ell-chromatic index for power graphs of cycles and general trees. Furthermore, we propose a polynomial-time coloring algorithm, for each studied class of graph, that satisfies the \ell-distance-edge-coloring.

Published
2010

32. Discussion on the (partial) Grundy and b-chromatic numbers of graphs

Author

Effantin, Brice, Kheddouci, Hamamache, Laboratoire d'Informatique pour l'Entreprise et les Systèmes de Production (LIESP), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), and Université de Lyon

Subjects
Mathematics::Combinatorics, Computer Science::Discrete Mathematics, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract

International audience; The b-chromatic and Grundy colorings are two proper colorings of the vertices of a graph which maximize the number of colors used. While the b-chromatic coloring determines, for every color, a vertex adjacent to all the other colors, the Grundy coloring allows each vertex with color c to be adjacent to colors 1 to c-1. The constraints of each coloring imply that they are difficult to compare. The partial Grundy coloring, which have for every color a vertex adjacent to all the lower colors than its, is defined as a relaxed Grundy coloring, and could be see also as a relaxed b-chromatic coloring. From this remark, could it be considered as a point of reference to relate the b-chromatic and Grundy colorings? In this paper, we present three graph parameters, linked to these colorings, and we discuss the relations between them.

Published
2008

33. [r,s,t]-coloring of Trees and Bipartite graphs

Author

Dekar, L., Effantin, Brice, Kheddouci, Hamamache, Equipe, Graphe Liesp, Laboratoire d'Informatique pour l'Entreprise et les Systèmes de Production (LIESP), 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)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon, and Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL)

Subjects
[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-NI] Computer Science [cs]/Networking and Internet Architecture [cs.NI], [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Generalized coloring, Total coloring, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [r,s,t]-coloring, Stars, ComputingMilieux_MISCELLANEOUS, Bipartite graphs, Trees
Abstract

Let G=(V,E) be a graph with vertex set V and edge set E. Given non-negative integers r, s and t, an [r,s,t]-coloring of a graph G is a function c from V(G)∪E(G) to the color set {0,1,…,k−1} such that |c(vi)−c(vj)|≥r for every two adjacent vertices vi, vj∈V, |c(ei)−c(ej)|≥s for every two adjacent edges ei, ej∈E, and |c(vi)−c(ej)|≥t for every vertex vi and its incident edge ej. Thus, an [r,s,t]-coloring is a generalization of the total coloring and the classical vertex and edge colorings of graphs. The [r,s,t]-coloring can have many applications in different fields like scheduling [A. Kemnitz, M. Marangio, [r,s,t]-colorings of graphs, Discrete Mathematics 307 (2) (2007) 199–207], channel assignment problem [F. Bazzaro, M. Montassier, A. Raspaud, (d,1)-total labelling of planar graphs with large girth and high maximum degree, Discrete Mathematics 307 (2007) 2141–2151], etc. The [r,s,t]-chromatic number χr,s,t(G) of G is the minimum k such that G admits an [r,s,t]-coloring. In our paper, we give exact values (or bounds in one case) of the [r,s,t]-chromatic number of stars, for every positive r, s and t. We also provide exact values and some tight bounds of this parameter for trees and bipartite graphs.

Published
2007

34. Exact values for the b-chromatic number of a power complete k-ary tree

Author

Effantin, Brice, Kheddouci, Hamamache, Laboratoire d'Informatique pour l'Entreprise et les Systèmes de Production (LIESP), 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), 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)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), and Université de Lyon

Subjects
b-chromatic number, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], graph coloring, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], tree
Abstract

International audience; Let G be a graph on vertices x1, x2, . . . , xn. The b-chromatic number of G is defined as the maximum number k of colors that can be used to color the vertices of G, such that we obtain a proper coloring and each color i, with 1 ≤ i ≤ k, has at least one representant xi adjacent to a vertex of every color j, 1 ≤ j != i ≤ k. In this paper, we give the exact value for the b-chromatic number of power graphs of a complete binary tree.

Published
2005

44. -coloring of trees and bipartite graphs

Author

Dekar, Lyes, Effantin, Brice, and Kheddouci, Hamamache

Subjects
*GRAPH coloring, *TREE graphs, *BIPARTITE graphs, *GRAPH labelings, *COMBINATORICS, *TOPOLOGICAL degree
Abstract

Abstract: Let be a graph with vertex set and edge set . Given non-negative integers , and , an -coloring of a graph is a function from to the color set such that for every two adjacent vertices , , for every two adjacent edges , , and for every vertex and its incident edge . Thus, an -coloring is a generalization of the total coloring and the classical vertex and edge colorings of graphs. The -coloring can have many applications in different fields like scheduling [A. Kemnitz, M. Marangio, -colorings of graphs, Discrete Mathematics 307 (2) (2007) 199–207], channel assignment problem [F. Bazzaro, M. Montassier, A. Raspaud, -total labelling of planar graphs with large girth and high maximum degree, Discrete Mathematics 307 (2007) 2141–2151], etc. The -chromatic number of is the minimum such that admits an -coloring. In our paper, we give exact values (or bounds in one case) of the -chromatic number of stars, for every positive , and . We also provide exact values and some tight bounds of this parameter for trees and bipartite graphs. [Copyright &y& Elsevier]

Published
2010
Full Text
View/download PDF

45. The b-chromatic number of some power graphs.

Author

Effantin, Brice and Kheddouci, Hamamache

Subjects
*GRAPHIC methods, *COLORS, *COMPUTATIONAL mathematics, *VERTEX operator algebras, *MATHEMATICS
Abstract

Let G be a graph on vertices v1,, v2,..., vn. The b-chromatic number of G is defined as the maximum number k of colors that can be used to color the vertices of G, such that we obtain a proper coloring and each color i, with 1 ≤ i &;le; k, has at least one representant xi adjacent to a vertex of every color j, 1 ≤ j ≠ i ≤ k. In this paper, we give the exact value for the b-chromatic number of power graphs of a path and we determine bounds for the b-chromatic number of power graphs of a cycle. [ABSTRACT FROM AUTHOR]

Published
2003

46. Diversified top-ksearch with relaxed graph simulation

Author

Habi, Abdelmalek, Effantin, Brice, and Kheddouci, Hamamache

Abstract

Graph pattern matching has been widely used in a broad spectrum of real-world applications, and it has been the subject of several investigations, mainly of its importance and use. In this context, different models along with their appropriate algorithms have been proposed. However, in addition to the excessive processing costs, most of the existing models suffer from the failing query problem due to their limitations on finding meaningful matches. Also, in some scenarios, the number of matches may be enormous, making the inspection a daunting task. In this work, we introduce a new model for graph pattern matching, called relaxed graph simulation(RGS), allowing the relaxation of queries to identify more significant matches and to avoid the empty-set answer problem. We then formalize and study the top-kmatching problem based on two function classes, relevance and diversity, for ranking the matches with respect to the proposed model. We also formalize and investigate the diversified top-kmatching problem, and we propose a diversification function to balance relevance and diversity. Nonetheless, we provide efficient algorithms based on optimization strategies to compute the top-kand the diversified top-kmatches according to the RGSmodel. Our experimental results, on four real datasets, demonstrate both the effectiveness and the efficiency of the proposed approaches.

Published
2019
Full Text
View/download PDF

47. Search and Aggregation in XML Documents

Author

Abdelmalek Habi, Hamamache Kheddouci, Brice Effantin, Effantin, Brice, Appel à projets générique - Recherche d'Information Agrégative et Contextuelle - - CAIR2014 - ANR-14-CE23-0006 - Appel à projets générique - VALID, Graphes, AlgOrithmes et AppLications (GOAL), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), 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), and ANR-14-CE23-0006,CAIR,Recherche d'Information Agrégative et Contextuelle(2014)

Subjects
Document Structure Description, Computer science, computer.internet_protocol, Efficient XML Interchange, XML Signature, Well-formed document, 02 engineering and technology, computer.software_genre, Simple API for XML, XML Schema Editor, 0202 electrical engineering, electronic engineering, information engineering, XML schema, computer.programming_language, Information retrieval, 05 social sciences, XML validation, computer.file_format, XML framework, XML database, [INFO.INFO-IR]Computer Science [cs]/Information Retrieval [cs.IR], ComputingMethodologies_DOCUMENTANDTEXTPROCESSING, 020201 artificial intelligence & image processing, [INFO.INFO-IR] Computer Science [cs]/Information Retrieval [cs.IR], 0509 other social sciences, 050904 information & library sciences, computer, XML, XML Catalog
Abstract

International audience; Information retrieval encounters a migration from the traditional paradigm (returning an ordered list of responses) to the aggregate search paradigm (grouping the most comprehensive and relevant answers into one final aggregated document). Nowadays extensible markup language (XML) is an important standard of information exchange and representation. Usually the tree representation of documents and queries is used to process them. It allows to consider the XML documents retrieval as a tree matching problem between the document trees and the query tree. Several paradigms for retrieving XML documents have been proposed in the literature but only a few of them try to aggregate a set of XML documents in order to provide more significant answers for a given query. In this paper, we propose and evaluate an aggregated search method to obtain the most accurate and richest answers in XML fragment search. Our search method is based on the Top-k Approximate Subtree Matching (TASM) algorithm and a new similarity function is proposed to improve the returned fragments. Then an aggregation process is presented to generate a single aggregate response containing the most relevant, exhaustive and non-redundant information given by the fragments. The method is evaluated on two real world datasets. Experimentations show that it generates good results in terms of relevance and quality.

Published
2017

48. [r,s,t]-colorings of graph products

Author

Hamamache Kheddouci, Brice Effantin, Lyes Dekar, Laboratoire d'Informatique pour l'Entreprise et les Systèmes de Production (LIESP), 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), Graphes, AlgOrithmes et AppLications (GOAL), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), 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), and Effantin, Brice

Subjects
Discrete mathematics, 010102 general mathematics, Neighbourhood (graph theory), Total coloring, 0102 computer and information sciences, Complete coloring, Direct product, 16. Peace & justice, 01 natural sciences, Graph coloring, Theoretical Computer Science, Vertex (geometry), Combinatorics, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], Edge coloring, MSC 05C15, 010201 computation theory & mathematics, Independent set, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Cartesian product, Discrete Mathematics and Combinatorics, 0101 mathematics, Fractional coloring, Mathematics
Abstract

International audience; Let G = (V,E) be a graph with vertex set V and edge set E. Given non negative integers r, s and t, an [r, s, t]-coloring of a graph G is a proper total coloring where the neighboring elements of G (vertices and edges) receive colors with a certain difference r between colors of adjacent vertices, a difference s between colors of adjacent edges and a difference t between colors of a vertex and an incident edge. Thus [r, s, t]-colorings generalize the classical colorings of graphs and can have applications in different fields like scheduling, channel assignment problem, etc. The [r, s, t]-chromatic number of G is the minimum k such that G admits an [r, s, t]-coloring. In our paper we propose several bounds for the [r, s, t]-chromatic number of the cartesian and direct products of some graphs.

Published
2014

49. New Results about Set Colorings of Graphs

Author

Jean-Pierre Boutin, Brice Effantin, Hamamache Kheddouci, Hamida Seba, Eric Duchêne, Graphes, Apprentissage et Multi-Agents (GAMA), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon, Graphes, AlgOrithmes et AppLications (GOAL), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), 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), and Effantin, Brice

Subjects
ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION, 010103 numerical & computational mathematics, 0102 computer and information sciences, 01 natural sciences, Theoretical Computer Science, Combinatorics, Greedy coloring, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Discrete Mathematics and Combinatorics, Graph coloring, 0101 mathematics, List coloring, Mathematics, Discrete mathematics, Applied Mathematics, Complete coloring, Brooks' theorem, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], Edge coloring, MSC 05C15, Computational Theory and Mathematics, 010201 computation theory & mathematics, Graph Coloring, Maximal independent set, Geometry and Topology, Fractional coloring, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

International audience; The set coloring problem is a new kind of both vertex and edge coloring of a graph introduced by Suresh Hegde in 2009. Only large bounds have been given on the chromatic number for general graphs. In this paper, we consider the problem on paths and complete binary trees, and show that it can be reduced to the computation of a transversal in a special Latin square, i.e., the XOR table. We then investigate a variation of the problem called strong set coloring, and we provide an exhaustive list of all graphs being strongly set colorable with at most 4 colors.

Published
2010

50. A fully dynamic distributed algorithm for a b-coloring of graphs

Author

Brice Effantin, Shuang Liu, Hamamache Kheddouci, Laboratoire d'Informatique pour l'Entreprise et les Systèmes de Production (LIESP), 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), and Effantin, Brice

Subjects
Discrete mathematics, Theoretical computer science, algorithm, Computer science, Multigraph, dynamic algorithm, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Voltage graph, ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Butterfly graph, law.invention, Edge coloring, law, Graph power, Line graph, graph coloring, Graph coloring, Graph factorization, ComputingMethodologies_COMPUTERGRAPHICS
Abstract

International audience; A b-coloring of a graph G is a proper coloring of the nodes of G such that each color class contains a node that has a neighbor in all other color classes. A fully dynamic algorithm is an algorithm used to support modifications (insertion or deletion) of nodes and edges in a network. Thus, in this paper we propose a fully dynamic distributed algorithm to maintain a b-coloring of a graph when its topology evolves. This method determines a b-coloring in time O(D²) and needs O(nD) changes of colors to maintain a b-coloring of a graph, where n is the number of nodes and D is the maximum degree in the graph.

Published
2008

Catalog

Books, media, physical & digital resources
See catalog results