5documents trouvés
Dense and sparse graph partition
J.DARLAY, N.BRAUNER, J.MONCEL
G-SCOP, MOGISA
Revue Scientifique : Discrete Applied Mathematics, Vol.160, N°16-17, pp.2389-2396, Novembre 2012 , N° 11401
Diffusable
128110Generic algorithms for some decision problems on fasciagraphs and rotagraphs
M.BOUZNIF, J.MONCEL, M.PREISSMANN
G-SCOP, MOGISA
Revue Scientifique : Discrete Mathematics, Vol.312, N°17, pp.2707-2719, Septembre 2012 , N° 11546
Diffusable
128108A note on single-machine scheduling problems with position-dependent processing times
J.MONCEL, G.FINKE, V.JOST
MOGISA, G-SCOP, LIX
Rapport LAAS N°11844, Avril 2012, 6p.
Lien : http://hal.archives-ouvertes.fr/hal-00647789
Diffusable
Plus d'informations
Abstract
The purpose of this note is two-fold. First, it answers an open prob- lem about a single-machine scheduling problem with exponential position-dependent processing times de ned in [V. S. Gordon, C. N. Potts, V. A.Strusevich, J. D. Whitehead, Single machine scheduling models with deterioration and learning: Handling precedence constraints via priority generation, Journal of Scheduling 11 (2008), 357{370]. In this problem, the processing time of job i when scheduled in rank r is equal to p(i; r) = pir-1,with a positive constant. Gordon et al show in the above-mentioned paper with priority-generating techniques that the problem of minimizing the total ow-time on one machine admits an O(n log n) algorithm when 2]0; 1[[[2;+1[, and leave the case 2 [1; 2[ open. We show that the problem admits an O(n log n) algorithm also for 2 [1; 2[. The second purpose of this note is to provide a simple and general insight on why and when position-dependent scheduling problems on one machine can be solved in time O(n log n).
New results on variants of covering codes in Sierpinski graphs
S.GRAVIER, M.KOVSE, M.MOLLARD, J.MONCEL, A.PARREAU
UJF, Univ. of Maribor, MOGISA
Rapport LAAS N°11400, Juillet 2011, 8p.
Lien : http://hal.archives-ouvertes.fr/hal-00656467/fr/
Diffusable
Plus d'informations
Abstract
In this paper we study identifying codes, locating-dominating codes, and total-dominating codes in Sierpinski graphs. We compute the minimum size of such codes in Sierpinski graphs
Adaptive identification in Torii in the king lattice
Y.BEN HAIM, S.GRAVIER, A.LOBSTEIN, J.MONCEL
IBM Israel, UJF, Institut Telecom, MOGISA
Revue Scientifique : Electronic Journal of Combinatorics, Vol.18, N°1, 18p., Mai 2011 , N° 11393
Diffusable
125018