Zobrazeno 1 - 10
of 49
pro vyhledávání: '"Christian Laforest"'
Autor:
Alexis Cornet, Christian Laforest
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol Vol. 19 no. 3, Iss Graph Theory (2017)
Total dominating set, connected vertex cover and Steiner tree are well-known graph problems. Despite the fact that they are NP-complete to optimize, it is easy (even trivial) to find solutions, regardless of their size. In this paper, we study a vari
Externí odkaz:
https://doaj.org/article/233523eef0c84d108ab9b4b9f706cc92
Autor:
Christian Laforest
Un graphe est un objet abstrait très simple, composé d'éléments (les sommets) et de relations entre ces éléments (les arêtes). Un graphe permet de représenter des liens d'amitié entre des gens, des lignes aériennes entre des villes, des câ
Autor:
Christian Laforest, Timothée Martinod
Publikováno v:
Theoretical Computer Science
Theoretical Computer Science, 2022, 904, pp.1-14. ⟨10.1016/j.tcs.2021.05.018⟩
Theoretical Computer Science, 2022, 904, pp.1-14. ⟨10.1016/j.tcs.2021.05.018⟩
A subset $D \subseteq V$ is an \emph{independent} (or \emph{stable}) \emph{dominating set} of a graph $G = (V,E)$ if $D$ is an independent set (no edges between vertices of $D$) and dominates all the vertices of $G$ (each vertex of $V-D$ has a neighb
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::08c2d6161f08f8acb1f1df1506c422bc
https://hal.science/hal-04043902
https://hal.science/hal-04043902
Autor:
Christian Laforest, Alexis Cornet
Publikováno v:
Combinatorial Optimization and Applications-12th International Conference, COCOA 2018
Combinatorial Optimization and Applications-12th International Conference, COCOA 2018, Dec 2018, Atlanta, United States. pp.183--197
Combinatorial Optimization and Applications ISBN: 9783030046507
COCOA
[Research Report] LIMOS (UMR CNRS 6158), université Clermont Auvergne, France. 2018
Combinatorial Optimization and Applications-12th International Conference, COCOA 2018, Dec 2018, Atlanta, United States. pp.183--197
Combinatorial Optimization and Applications ISBN: 9783030046507
COCOA
[Research Report] LIMOS (UMR CNRS 6158), université Clermont Auvergne, France. 2018
In this paper we study variants of well-known graph problems: vertex cover, connected vertex cover, dominating set, total dominating set, independent dominating set, spanning tree, connected minimum weighted spanning graph, matching and hamiltonian p
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::275332dc7571c35eb2a2e26678e41871
https://hal.archives-ouvertes.fr/hal-01977760
https://hal.archives-ouvertes.fr/hal-01977760
Autor:
Christian Laforest, Alexis Cornet
Publikováno v:
Discrete Applied Mathematics
Discrete Applied Mathematics, 2018, 244, pp.78-88
Discrete Applied Mathematics, Elsevier, 2018, 244, pp.78-88
Discrete Applied Mathematics, 2018, 244, pp.78-88
Discrete Applied Mathematics, Elsevier, 2018, 244, pp.78-88
Domination problems have been studied in graph theory for decades. In most of them, it is NP-complete to find an optimal solution, while it is easy (and even trivial in some cases) to find a solution in polynomial time, regardless of its size. In rec
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::7fa0af5c0262cef28b11fd5a54e1b49c
https://hal.science/hal-01977737
https://hal.science/hal-01977737
Autor:
Christian Laforest
Publikováno v:
EDP-sciences, 2017
Un graphe est un objet abstrait tres simple, compose d'elements (les sommets) et de relations entre ces elements (les aretes). Un graphe permet de representer des liens d'amitie entre des gens, des lignes aeriennes entre des villes, des câbles entre
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5027b1e832a8c4df2575fa5c803d9ba7
https://hal.archives-ouvertes.fr/hal-01979220
https://hal.archives-ouvertes.fr/hal-01979220
Autor:
Christian Laforest, Raksmey Phan
Publikováno v:
RAIRO - Operations Research. 47:199-221
In this paper we present a new approach to solve the Minimum Independent Dominating Set problem in general graphs which is one of the hardest optimization problem. We propose a method using a clique partition of the graph, partition that can be obtai
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::497405861ae7eff3373c24bb5760d6b4
https://doi.org/10.1051/ro/2013034
https://doi.org/10.1051/ro/2013034
Publikováno v:
Information Processing Letters
Information Processing Letters, Elsevier, 2009, 109 (9), pp.436--439. ⟨10.1016/j.ipl.2008.12.021⟩
Information Processing Letters, 2009, 109 (9), pp.436--439. ⟨10.1016/j.ipl.2008.12.021⟩
Information Processing Letters, Elsevier, 2009, 109 (9), pp.436--439. ⟨10.1016/j.ipl.2008.12.021⟩
Information Processing Letters, 2009, 109 (9), pp.436--439. ⟨10.1016/j.ipl.2008.12.021⟩
International audience; In 2005, Demange and Paschos proposed in [M. Demange, V.Th. Paschos, On-line vertex-covering, Theoret. Comput. Sci. 332 (2005) 83-108] an online algorithm (noted LR here) for the classical vertex cover problem. They shown that
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2dee2c7eaa0a1553d7d6c64158577f91
https://doi.org/10.1016/j.ipl.2008.12.021
https://doi.org/10.1016/j.ipl.2008.12.021
Publikováno v:
Parallel Processing Letters. 14:315-323
We consider the problem of scheduling a set of independent tasks (with release dates and deadlines) on a set of parallel identical machines. Our objective is to find a schedule maximizing simultaneously two objectives, namely the weight of scheduled
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::681c189a78375604b1b98448a5f6dad3
https://doi.org/10.1142/s0129626404001891
https://doi.org/10.1142/s0129626404001891
Publikováno v:
18th International Conference on Principles of Distributed Systems, OPODIS 2014
18th International Conference on Principles of Distributed Systems, OPODIS 2014, Dec 2014, Cortina d’Ampezzo, Italy. pp.307-322, ⟨10.1007/978-3-319-14472-6_21⟩
Lecture Notes in Computer Science ISBN: 9783319144719
OPODIS
18th International Conference on Principles of Distributed Systems, OPODIS 2014, Dec 2014, Cortina d’Ampezzo, Italy. pp.307-322, ⟨10.1007/978-3-319-14472-6_21⟩
Lecture Notes in Computer Science ISBN: 9783319144719
OPODIS
International audience; In many wireless networks, there is no fixed physical backbone nor centralized network management. The nodes of such a network have to self-organize in order to maintain a virtual backbone used to route messages. Moreover, any
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::990b3238b04773bc8068f5a81315d5e6
https://hal.science/hal-01219847/document
https://hal.science/hal-01219847/document