Zobrazeno 1 - 10
of 19
pro vyhledávání: '"David Auger"'
Publikováno v:
Discrete Applied Mathematics. 161:1674-1685
We introduce the notion of watching systems in graphs, which is a generalization of that of identifying codes. We give some basic properties of watching systems, an upper bound on the minimum size of a watching system, and results on the graphs which
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1177fcd0a7543ee7bf8ff729f107e7ae
https://doi.org/10.1016/j.dam.2011.04.025
https://doi.org/10.1016/j.dam.2011.04.025
Autor:
David Auger, Olivier Teytaud
Publikováno v:
International Journal of Foundations of Computer Science. 23:1439-1450
The classical decision problem associated with a game is whether a given player has a winning strategy, i.e. some strategy that leads almost surely to a victory, regardless of the other players' strategies. While this problem is relevant for determin
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::ea36298335d4caf8b8f20ec1e0f20ca9
https://doi.org/10.1142/s0129054112400576
https://doi.org/10.1142/s0129054112400576
Publikováno v:
Designs, Codes and Cryptography. 70:3-7
In any connected, undirected graph G = (V, E), the distance d(x, y) between two vertices x and y of G is the minimum number of edges in a path linking x to y in G. A sphere in G is a set of the form S r (x) = {y ? V : d(x, y) = r}, where x is a verte
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::c109f4012666991dc0df6019639f62e7
https://doi.org/10.1007/s10623-012-9638-x
https://doi.org/10.1007/s10623-012-9638-x
Autor:
David Auger, Iiro S. Honkala
Publikováno v:
Graphs and Combinatorics. 29:333-347
We consider the infinite King grid where we investigate properties of watching systems, an extension of the notion of identifying code recently introduced by Auger et al. (Discret. Appl. Math., 2011). The latter were extensively studied in the infini
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::7100b1ea22e3940d5f5531d396920e13
https://doi.org/10.1007/s00373-011-1124-0
https://doi.org/10.1007/s00373-011-1124-0
Autor:
David Auger
Publikováno v:
4OR. 9:417-420
This is a summary of the author’s PhD thesis supervised by Pr. Olivier Hudry and defended on 7th June 2010 at Telecom ParisTech. The thesis is written in French (introduction and overview of results) and English (articles, which contain the proofs)
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::848b21b4c9a39123adb42180dc194482
https://doi.org/10.1007/s10288-011-0167-7
https://doi.org/10.1007/s10288-011-0167-7
Publikováno v:
International Transactions in Operational Research. 17:691-710
Let G be a simple, undirected, connected graph with vertex set V(G) and ⊆V(G) be a set of vertices whose elements are called codewords. For v∈V(G) and r1, let us denote by Ir(v) the set of codewords c∈ such that d(v, c)r, where the distance d(v
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::f057476179b35d7b8e12d5f0d91bb99c
https://doi.org/10.1111/j.1475-3995.2009.00750.x
https://doi.org/10.1111/j.1475-3995.2009.00750.x
Autor:
David Auger
Publikováno v:
European Journal of Combinatorics. 31:1372-1384
Let G be a finite undirected graph with vertex set V(G). If [email protected]?V(G), let N[v] denote the closed neighbourhood of v, i.e. v itself and all its adjacent vertices in G. An identifying code in G is a subset C of V(G) such that the sets N[v
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::fcb783639cad17f9cb0618c8cb15522d
https://doi.org/10.1016/j.ejc.2009.11.012
https://doi.org/10.1016/j.ejc.2009.11.012
Publikováno v:
Advances in Mathematics of Communications. 3:97-114
Consider a connected, undirected graph $G=(V,E)$ and an integer $r \geq 1$; for any vertex $v\in V$, let $B_r(v)$ denote the ball of radius $r$ centred at $v$, i.e., the set of all vertices linked to $v$ by a path consisting of at most $r$ edges. If
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::0741edc1285d520bceb852119bf48075
https://doi.org/10.3934/amc.2009.3.97
https://doi.org/10.3934/amc.2009.3.97
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783319060880
TAMC
TAMC
The optimal value computation for turned-based stochastic games with reachability objectives, also known as simple stochastic games, is one of the few problems in NP ∩ coNP which are not known to be in P. However, there are some cases where these g
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::7fa5e030f87249b32896768ddf41ee46
https://doi.org/10.1007/978-3-319-06089-7_6
https://doi.org/10.1007/978-3-319-06089-7_6
Publikováno v:
28th International Symposium on Computer and Information Sciences (ISCIS)
28th International Symposium on Computer and Information Sciences (ISCIS), Oct 2013, Paris, France
Information Sciences and Systems 2013 ISBN: 9783319016030
ISCIS
28th International Symposium on Computer and Information Sciences (ISCIS), Oct 2013, Paris, France
Information Sciences and Systems 2013 ISBN: 9783319016030
ISCIS
The Max-Cut problem consists in splitting in two parts the set of vertices of a given graph so as to maximize the sum of weights of the edges crossing the partition. We here address the problem of computing locally maximum cuts in general undirected
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::38afb592003787dcd7b1f1012d0acabe
https://hal.archives-ouvertes.fr/hal-01301187
https://hal.archives-ouvertes.fr/hal-01301187