-
L. Addario-Berry,
K. Dalal,
C. McDiarmid,
B. Reed,
and A. Thomason.
Vertex Colouring Edge Weightings.
Combinatorica,
27:1-12,
2007.
@Article{ADM+07,
author = {L. Addario-Berry and K. Dalal and C. McDiarmid and B. Reed and A. Thomason},
title = {Vertex Colouring Edge Weightings},
journal = {Combinatorica},
year = {2007},
OPTkey = {},
volume = {27},
OPTnumber = {},
pages = {1-12},
OPTmonth = {},
OPTannote = {},
sorte = "rev-int",
}
-
L. Addario-Berry,
F. Havet,
and S. Thomassé.
Paths with two blocks in $n$-chromatic digraphs.
Journal of Combinatorial Theory Ser. B,
97:620--626,
2007.
[PDF
]
@ARTICLE{AHT07,
AUTHOR={L. Addario-Berry and F. Havet and S. Thomass\'e},
TITLE={Paths with two blocks in $n$-chromatic digraphs},
JOURNAL = "Journal of Combinatorial Theory Ser. B",
VOLUME = "97",
YEAR = "2007",
PAGES = "620--626",
PDF = {ftp://ftp-sop.inria.fr/mascotte/Publications/AHT07.pdf},
sorte = "rev-int",
}
-
E. Alba,
B. Dorronsoro,
F. Luna,
A.J. Nebro,
P. Bouvry,
and L. Hogie.
A cellular multi-objective genetic algorithm for optimal broadcasting strategy in metropolitan MANETs.
Computer Communications,
30(4):685--697,
August 2007.
[WWW
]
| Abstract: |
|
Mobile Ad-hoc Networks (MANETs) are composed of a set of communicating devices which are able to spontaneously interconnect without any pre-existing infrastructure. In such scenario, broadcasting becomes an operation of capital importance for the own existence and operation of the network. Optimizing a broadcast strategy in MANETs is a multi-objective problem accounting for three goals: reaching as many stations as possible, minimizing the network utilization, and reducing the makespan. In this paper, we study the fine-tuning of broadcast strategies by using a cellular multi-objective genetic algorithm (cMOGA) that computes a Pareto front of the solutions to empower a human designer with the ability of choosing the preferred configuration for the network. We define two formulations of the problem, one with three objectives and another one with two objectives plus a constraint. Our experiments using a complex and realistic MANET simulator reveal that using cMOGA is a promising approach to solve the optimum broadcast problem. |
@ARTICLE{ADL+07,
OPTauthor = {Enrique Alba and Bernab{\'e} Dorronsoro and Francisco Luna and Antonio J. Nebro and Pascal Bouvry and L. Hogie},
author = {E. Alba and B. Dorronsoro and F. Luna and A.J. Nebro and P. Bouvry and L. Hogie},
title = {A cellular multi-objective genetic algorithm for optimal broadcasting strategy in metropolitan MANETs},
journal = {Computer Communications},
year = {2007},
volume = {30},
pages = {685--697},
number = {4},
month = {August},
abstract = {Mobile Ad-hoc Networks (MANETs) are composed of a set of communicating devices which are able to spontaneously interconnect without any pre-existing infrastructure. In such scenario, broadcasting becomes an operation of capital importance for the own existence and operation of the network. Optimizing a broadcast strategy in MANETs is a multi-objective problem accounting for three goals: reaching as many stations as possible, minimizing the network utilization, and reducing the makespan. In this paper, we study the fine-tuning of broadcast strategies by using a cellular multi-objective genetic algorithm (cMOGA) that computes a Pareto front of the solutions to empower a human designer with the ability of choosing the preferred configuration for the network. We define two formulations of the problem, one with three objectives and another one with two objectives plus a constraint. Our experiments using a complex and realistic MANET simulator reveal that using cMOGA is a promising approach to solve the optimum broadcast problem.},
address = {Newton, MA, USA},
doi = {10.1109/IPDPS.2005.4},
issn = {0140-3664},
publisher = {Butterworth-Heinemann},
url = {http://www.springerlink.com/content/qk6747wq32478r42/fulltext.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={no},
OPTx-international-audience={yes},
sorte = "rev-int",
}
-
R. Bayon,
N. Lygeros,
and J.-S. Sereni.
Orders with ten elements are circle orders.
Applied Mathematics E-Notes,
7:16--22,
2007.
[WWW
] [PDF
]
@Article{BLS07a,
author = {R. Bayon and N. Lygeros and J.-S. Sereni},
title = {Orders with ten elements are circle orders},
journal = {Applied Mathematics E-Notes},
year = {2007},
volume = {7},
pages = {16--22},
URL={http://www.math.nthu.edu.tw/~amen/},
PDF={http://kam.mff.cuni.cz/~sereni/Articles/BLS07a.pdf},
sorte = "rev-int",
}
-
J-C. Bermond,
L. Braud,
and D. Coudert.
Traffic Grooming on the Path.
Theoretical Computer Science,
384(2-3):139-151,
October 2007.
[WWW
] [PDF
]
| Abstract: |
|
In a WDM network, routing a request consists in assigning it a route in the physical network and a wavelength. If each request uses at most 1/C of the bandwidth of the wavelength, we will say that the grooming factor is C. That means that on a given edge of the network we can groom (group) at most C requests on the same wavelength. With this constraint the objective can be either to minimize the number of wavelengths (related to the transmission cost) or minimize the number of Add Drop Multiplexers (shortly ADM) used in the network (related to the cost of the nodes). We consider here the case where the network is a path on N nodes, P_N. Thus the routing is unique. For a given grooming factor C minimizing the number of wavelengths is an easy problem, well known and related to the load problem. But minimizing the number of ADM's is NP-complete for a general set of requests and no results are known. Here we show how to model the problem as a graph partition problem and using tools of design theory we completely solve the case where C=2 and where we have a static uniform all-to-all traffic (one request for each pair of vertices). |
@ARTICLE{BBC07,
author = {J-C. Bermond and L. Braud and D. Coudert},
title = {Traffic Grooming on the Path},
journal = {Theoretical Computer Science},
year = {2007},
month = oct,
volume = {384},
pages = {139-151},
number = {2-3},
abstract = {In a WDM network, routing a request consists in assigning it a route in the physical network and a wavelength. If each request uses at most 1/C of the bandwidth of the wavelength, we will say that the grooming factor is C. That means that on a given edge of the network we can groom (group) at most C requests on the same wavelength. With this constraint the objective can be either to minimize the number of wavelengths (related to the transmission cost) or minimize the number of Add Drop Multiplexers (shortly ADM) used in the network (related to the cost of the nodes). We consider here the case where the network is a path on N nodes, P_N. Thus the routing is unique. For a given grooming factor C minimizing the number of wavelengths is an easy problem, well known and related to the load problem. But minimizing the number of ADM's is NP-complete for a general set of requests and no results are known. Here we show how to model the problem as a graph partition problem and using tools of design theory we completely solve the case where C=2 and where we have a static uniform all-to-all traffic (one request for each pair of vertices).},
optnote = {A preliminary version has been presented at SIROCCO'05.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/BBC-to-tcsa.pdf},
url = {http://dx.doi.org/10.1016/j.tcs.2007.04.028},
sorte = "rev-int"
}
-
J-C. Bermond,
A. Ferreira,
S. Pérennes,
and J. Peters.
Neighbourhood Broadcasting in Hypercubes.
SIAM Journal on Discrete Mathematics,
21(4):823-843,
2007.
[PDF
]
| Abstract: |
|
In the broadcasting problem, one node needs to broadcast a message to all other nodes in a network. If nodes can only communicate with one neighbor at a time, broadcasting takes at least $\lceil \log_2 N \rceil$ rounds in a network of $N$ nodes. In the neighborhood broadcasting problem, the node that is broadcasting needs to inform only its neighbors. In a binary hypercube with $N$ nodes, each node has $\log_2 N$ neighbors, so neighborhood broadcasting takes at least $\lceil \log_2 \log_2 (N+1) \rceil$ rounds. In this paper, we present asymptotically optimal neighborhood broadcast protocols for binary hypercubes. |
@Article{BFPP07,
AUTHOR={J-C. Bermond and A. Ferreira and S. P\'erennes and J. Peters},
TITLE={Neighbourhood Broadcasting in Hypercubes},
journal = {SIAM Journal on Discrete Mathematics},
year = {2007},
Volume= {21},
Number={4},
Pages={823-843},
PDF={http://www-sop.inria.fr/members/Jean-Claude.Bermond/PUBLIS/BFPP07.pdf},
abstract={In the broadcasting problem, one node needs to broadcast a message to all other nodes in a network. If nodes can only communicate with one neighbor at a time, broadcasting takes at least $\lceil \log_2 N \rceil$ rounds in a network of $N$ nodes. In the neighborhood broadcasting problem, the node that is broadcasting needs to inform only its neighbors. In a binary hypercube with $N$ nodes, each node has $\log_2 N$ neighbors, so neighborhood broadcasting takes at least $\lceil \log_2 \log_2 (N+1) \rceil$ rounds. In this paper, we present asymptotically optimal neighborhood broadcast protocols for binary hypercubes.},
sorte = "rev-int"
}
-
J-C. Bermond and M-L. Yu.
Vertex disjoint routings of cycles over tori.
Networks,
49(3):217-225,
2007.
[PDF
]
@Article{BeYu07,
author = {J-C. Bermond and M-L. Yu},
title = {Vertex disjoint routings of cycles over tori},
journal = {Networks},
year = {2007},
Volume = {49},
Number = {3},
Pages = {217-225},
PDF = {http://www-sop.inria.fr/members/Jean-Claude.Bermond/PUBLIS/BeYu07.pdf},
sorte = "rev-int"
}
-
E. Birmelé,
J. A. Bondy,
and B. Reed.
The Erdos-Posa property for long circuits.
Combinatorica,
27:135-145,
2007.
@Article{BBR07b,
author = {E. Birmel\'e and J. A. Bondy and B. Reed},
title = {The {Erdos-Posa} property for long circuits},
journal = {Combinatorica},
year = {2007},
OPTkey = {},
volume = {27},
OPTnumber = {},
pages = {135-145},
OPTmonth = {},
OPTannote = {},
sorte = "rev-int",
}
-
P. Charbit,
S. Thomassé,
and A. Yeo.
The minimum feedback arc set problem is NP-hard for tournament.
Combinatorics, Probability and Computing,
16:1--4,
2007.
@article{CTY07,
author={P. Charbit and S. Thomass\'e and A. Yeo},
title={The minimum feedback arc set problem is {NP}-hard for tournament},
year={2007},
journal={Combinatorics, Probability and Computing},
volume={16},
number={},
pages = {1--4},
sorte = "rev-int",
}
-
A. Ciaffaglione,
L. Liquori,
and M. Miculan.
Reasoning about Object-based Calculi in (Co)Inductive Type Theory and the Theory of Contexts.
JAR, Journal of Automated Reasoning,
39:1--47,
2007.
[PDF
]
@article{CLM07,
author = {A. Ciaffaglione and L. Liquori and M. Miculan},
title = {Reasoning about Object-based Calculi in (Co)Inductive Type Theory and the Theory of Contexts},
year = {2007},
volume = {39},
pages = {1--47},
JOURNAL = {JAR, Journal of Automated Reasoning},
PDF = {http://www-sop.inria.fr/mascotte/Luigi.Liquori/PAPERS/jar-07.pdf},
sorte = "rev-int",
}
-
D. Coudert,
P. Datta,
S. Perennes,
H. Rivano,
and M-E. Voge.
Shared Risk Resource Group: Complexity and Approximability issues.
Parallel Processing Letters,
17(2):169-184,
June 2007.
[PDF
]
| Abstract: |
|
This article investigates complexity and approximability properties of combinatorial optimization problems yielded by the notion of Shared Risk Resource Group (SRRG). SRRG has been introduced in order to capture network survivability issues where a failure may break a whole set of resources, and has been formalized as colored graphs, where a set of resources is represented by a set of edges with same color. We consider here the analogous of classical problems such as determining paths or cuts with the minimum numbers of colors or color disjoint paths. These optimization problems are much more difficult than their counterparts in classical graph theory. In particular standard relationship such as the Max Flow - Min Cut equality do not hold any longer. In this article we identify cases where these problems are polynomial, for example when the edges of a given color form a connected subgraph, and otherwise give hardness and non approximability results for these problems. |
@ARTICLE{CDP+07,
author = {D. Coudert and P. Datta and S. Perennes and H. Rivano and M-E. Voge},
title = {Shared Risk Resource Group: Complexity and Approximability issues},
journal = {Parallel Processing Letters},
year = {2007},
volume = {17},
pages = {169-184},
number = {2},
month = jun,
abstract = {This article investigates complexity and approximability properties of combinatorial optimization problems yielded by the notion of Shared Risk Resource Group (SRRG). SRRG has been introduced in order to capture network survivability issues where a failure may break a whole set of resources, and has been formalized as colored graphs, where a set of resources is represented by a set of edges with same color. We consider here the analogous of classical problems such as determining paths or cuts with the minimum numbers of colors or color disjoint paths. These optimization problems are much more difficult than their counterparts in classical graph theory. In particular standard relationship such as the Max Flow - Min Cut equality do not hold any longer. In this article we identify cases where these problems are polynomial, for example when the edges of a given color form a connected subgraph, and otherwise give hardness and non approximability results for these problems.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/CDP+-PPL06.pdf},
sorte = "rev-int"
}
-
D. Coudert,
F. Huc,
and J.-S. Sereni.
Pathwidth of outerplanar graphs.
Journal of Graph Theory,
55(1):27-41,
May 2007.
[PDF
]
| Abstract: |
|
We are interested in the relation between the pathwidth of a biconnected outerplanar graph and the pathwidth of its (geometric) dual. Bodlaender and Fomin, after having proved that the pathwidth of every biconnected outerplanar graph is always at most twice the pathwidth of its (geometric) dual plus two, conjectured that there exists a constant c such that the pathwidth of every biconnected outerplanar graph is at most c plus the pathwidth of its dual. They also conjectured that this was actually true with c being one for every biconnected planar graph. Fomin proved that the second conjecture is true for all planar triangulations. First, we construct for each p>=1 a biconnected outerplanar graph of pathwidth 2p 1 whose (geometric) dual has pathwidth p 1, thereby disproving both conjectures. Next, we also disprove two other conjectures (one of Bodlaender and Fomin, implied by one of Fomin). Finally we prove, in an algorithmic way, that the pathwidth of every biconnected outerplanar graph is at most twice the pathwidth of its (geometric) dual minus one. A tight interval for the studied relation is therefore obtained, and we show that all cases in the interval happen. |
@ARTICLE{CHS07,
author = {D. Coudert and F. Huc and J.-S. Sereni},
title = {Pathwidth of outerplanar graphs},
journal = {Journal of Graph Theory},
year = {2007},
volume = {55},
pages = {27-41},
number = {1},
month = may,
abstract = {We are interested in the relation between the pathwidth of a biconnected outerplanar graph and the pathwidth of its (geometric) dual. Bodlaender and Fomin, after having proved that the pathwidth of every biconnected outerplanar graph is always at most twice the pathwidth of its (geometric) dual plus two, conjectured that there exists a constant c such that the pathwidth of every biconnected outerplanar graph is at most c plus the pathwidth of its dual. They also conjectured that this was actually true with c being one for every biconnected planar graph. Fomin proved that the second conjecture is true for all planar triangulations. First, we construct for each p>=1 a biconnected outerplanar graph of pathwidth 2p 1 whose (geometric) dual has pathwidth p 1, thereby disproving both conjectures. Next, we also disprove two other conjectures (one of Bodlaender and Fomin, implied by one of Fomin). Finally we prove, in an algorithmic way, that the pathwidth of every biconnected outerplanar graph is at most twice the pathwidth of its (geometric) dual minus one. A tight interval for the studied relation is therefore obtained, and we show that all cases in the interval happen.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/CHS-JGT06.pdf},
sorte = "rev-int"
}
-
S. Fiorini,
N. Hardy,
B. Reed,
and A. Vetta.
Approximate min-max relations for odd cycles in planar graphs.
Mathematical Programming Ser. B,
110(1):71--91,
2007.
@article{FHRV07,
AUTHOR = {S. Fiorini and N. Hardy and B. Reed and A. Vetta},
TITLE = {Approximate min-max relations for odd cycles in planar graphs},
JOURNAL = {Mathematical Programming Ser. B},
SERIES = {B},
VOLUME = {110},
NUMBER = {1},
PAGES = {71--91},
YEAR = {2007},
sorte = "rev-int",
}
-
M. Flammini,
R. Klasing,
A. Navarra,
and S. Pérennes.
Improved approximation results for the Minimum Energy Broadcasting problem.
Algorithmica,
49(4):318-336,
2007.
[WWW
]
| Abstract: |
|
In this paper we present new results on the performance of the Minimum Spanning Tree heuristic for the Minimum Energy Broadcast Routing (MEBR) problem. We first prove that, for any number of dimensions dâ¥2, the approximation ratio of the heuristic does not increase when the power attenuation coefficient α, that is the exponent to which the coverage distance must be raised to give the emission power, grows. Moreover, we show that, for any fixed instance, as a limit for α going to infinity, the ratio tends to the lower bound of Clementi et al., Wan et al. given by the d-dimensional kissing number, thus closing the existing gap between the upper and the lower bound. We then introduce a new analysis allowing to establish a 7.45-approximation ratio for the 2-dimensional case, thus significantly decreasing the previously known 12 upper bound (actually corrected to 12.15 in Klasing et al.). Finally, we extend our analysis to any number of dimensions dâ¥2 and any αâ¥d, obtaining a general approximation ratio of 3 d â1, again independent of α. The improvements of the approximation ratios are specifically significant in comparison with the lower bounds given by the kissing numbers, as these grow at least exponentially with respect to d. |
@Article{FKNP07a,
title = { Improved approximation results for the Minimum Energy Broadcasting problem },
author = { M. Flammini and R. Klasing and A. Navarra and S. P\'erennes },
year = { 2007 },
journal = { Algorithmica },
pages = {318-336},
volume = {49},
number = {4},
OPTnote = { Published online on October 13th 2007},
abstract = {In this paper we present new results on the performance of the Minimum Spanning Tree heuristic for the Minimum Energy Broadcast Routing (MEBR) problem. We first prove that, for any number of dimensions dâ¥2, the approximation ratio of the heuristic does not increase when the power attenuation coefficient α, that is the exponent to which the coverage distance must be raised to give the emission power, grows. Moreover, we show that, for any fixed instance, as a limit for α going to infinity, the ratio tends to the lower bound of Clementi et al., Wan et al. given by the d-dimensional kissing number, thus closing the existing gap between the upper and the lower bound. We then introduce a new analysis allowing to establish a 7.45-approximation ratio for the 2-dimensional case, thus significantly decreasing the previously known 12 upper bound (actually corrected to 12.15 in Klasing et al.). Finally, we extend our analysis to any number of dimensions dâ¥2 and any αâ¥d, obtaining a general approximation ratio of 3 d â1, again independent of α. The improvements of the approximation ratios are specifically significant in comparison with the lower bounds given by the kissing numbers, as these grow at least exponentially with respect to d.},
url = {http://dx.doi.org/10.1007/s00453-007-9077-7},
sorte = "rev-int",
}
-
N. Fountoulakis and B. Reed.
Faster Mixing and Small Bottlenecks.
Probability Theory and Related Fields,
137:475-486,
2007.
@ARTICLE{FoRe07,
author = "N. Fountoulakis and B. Reed",
title = "Faster Mixing and Small Bottlenecks",
pages = "475-486",
journal = "Probability Theory and Related Fields",
volume = "137",
year = 2007,
sorte = "rev-int",
}
-
J. Galtier and A. Laugier.
Flow on data network and a positive semidefinite representable delay function.
Journal of Interconnection Networks,
8(1):29--43,
March 2007.
[PDF
]
| Abstract: |
|
Data networks are subject to congestion, thereby the delay to go across the network may be large enough in order to dishearten customers to keep on using such a network. In this paper we address the problem of determining in a given network a routing which minimizes the delay or keeps it under a certain bound. This problem was already shown as complete. Our main contribution is to study it in the special context of the positive semidefinite programming and we present a column generation approach to solve the underlying problem. |
@article{GaLa07,
author = {J. Galtier and A. Laugier},
title = {Flow on data network and a positive semidefinite representable delay function},
journal = {Journal of Interconnection Networks},
volume = {8},
number = {1},
year = {2007},
pages = {29--43},
month = mar,
PDF = {ftp://ftp-sop.inria.fr/mascotte/Publications/GaLa07.pdf},
abstract = {Data networks are subject to congestion, thereby the delay to go across the network may be large enough in order to dishearten customers to keep on using such a network. In this paper we address the problem of determining in a given network a routing which minimizes the delay or keeps it under a certain bound. This problem was already shown as complete. Our main contribution is to study it in the special context of the positive semidefinite programming and we present a column generation approach to solve the underlying problem.},
sorte = "rev-int"
}
-
L. Grigori,
M. Cosnard,
and E. G. Ng.
On the row merge for sparse LU factorization with partial pivoting.
BIT Numerical Mathematics,
47(1):45--76,
March 2007.
[PDF
]
| Abstract: |
|
We consider the problem of structure prediction for sparse LU factorization with partial pivoting. In this context, it is well known that the column elimination tree plays an important role for matrices satisfying an irreducibility condition, called the strong Hall property. Our primary goal in this paper is to address the structure prediction problem for matrices satisfying a weaker assumption, which is the Hall property. For this we consider the row merge matrix, an upper bound that contains the nonzeros in L and U for all possible row permutations that can be performed during the numerical factorization with partial pivoting. We discuss the row merge tree, a structure that represents information obtained from the row merge matrix; that is, information on the dependencies among the columns in Gaussian elimination with partial pivoting and on structural upper bounds of the factors L and U. We present new theoretical results that show that the nonzero structure of the row merge matrix can be described in terms of branches and subtrees of the row merge tree. These results lead to an efficient algorithm for the computation of the row merge tree, that uses as input the structure of A, and has a time complexity almost linear in the number of nonzeros in A. We also investigate experimentally the usage of the row merge tree for structure prediction purposes on a set of matrices that satisfy only the Hall property. We analyze in particular the size of upper bounds of the structure of L and U, the reordering of the matrix based on a postorder traversal and its impact on the factorization runtime. We show experimentally that for some matrices, the row merge tree is a preferred alternative to the column elimination tree. |
@article{GCN07,
author = {L. Grigori and M. Cosnard and E. G. Ng},
title = {On the row merge for sparse {LU} factorization with partial pivoting},
journal = {{BIT} Numerical Mathematics},
year = {2007},
volume = {47},
pages = {45--76},
number = {1},
month = mar,
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/GCN07.pdf},
abstract = {We consider the problem of structure prediction for sparse LU factorization with partial pivoting. In this context, it is well known that the column elimination tree plays an important role for matrices satisfying an irreducibility condition, called the strong Hall property. Our primary goal in this paper is to address the structure prediction problem for matrices satisfying a weaker assumption, which is the Hall property. For this we consider the row merge matrix, an upper bound that contains the nonzeros in L and U for all possible row permutations that can be performed during the numerical factorization with partial pivoting. We discuss the row merge tree, a structure that represents information obtained from the row merge matrix; that is, information on the dependencies among the columns in Gaussian elimination with partial pivoting and on structural upper bounds of the factors L and U. We present new theoretical results that show that the nonzero structure of the row merge matrix can be described in terms of branches and subtrees of the row merge tree. These results lead to an efficient algorithm for the computation of the row merge tree, that uses as input the structure of A, and has a time complexity almost linear in the number of nonzeros in A. We also investigate experimentally the usage of the row merge tree for structure prediction purposes on a set of matrices that satisfy only the Hall property. We analyze in particular the size of upper bounds of the structure of L and U, the reordering of the matrix based on a postorder traversal and its impact on the factorization runtime. We show experimentally that for some matrices, the row merge tree is a preferred alternative to the column elimination tree.},
sorte = "rev-int"
}
-
F. Honsell,
M. Lenisa,
and L. Liquori.
A Framework for Defining Logical Frameworks.
Electronic Notes in Theoretical Computer Science,
172:399 - 436,
2007.
Note: Computation, Meaning, and Logic: Articles dedicated to Gordon Plotkin.
[WWW
] [PDF
]
| Abstract: |
|
" In this paper, we introduce a General Logical Framework, called GLF, for defining Logical Frameworks, based on dependent types, in the style of the well known Edinburgh Logical Framework LF. The framework GLF features a generalized form of lambda abstraction where [beta]-reductions fire provided the argument satisfies a logical predicate and may produce an n-ary substitution. The type system keeps track of when reductions have yet to fire. The framework GLF subsumes, by simple instantiation, LF as well as a large class of generalized constrained-based lambda calculi, ranging from well known restricted lambda calculi, such as Plotkin's call-by-value lambda calculus, to lambda calculi with patterns. But it suggests also a wide spectrum of new calculi which have intriguing potential as Logical Frameworks. We investigate the metatheoretical properties of the calculus underpinning GLF and illustrate its expressive power. In particular, we focus on two interesting instantiations of GLF. The first is the Pattern Logical Framework (PLF), where applications fire via pattern-matching in the style of Cirstea, Kirchner, and Liquori. The second is the Closed Logical Framework (CLF) which features, besides standard [beta]-reduction, also a reduction which fires only if the argument is a closed term. For both these instantiations of GLF we discuss standard metaproperties, such as subject reduction, confluence and strong normalization. The GLF framework is particularly suitable, as a metalanguage, for encoding rewriting logics and logical systems, where rules require proof terms to have special syntactic constraints, e.g. logics with rules of proof, in addition to rules of derivations, such as, e.g., modal logic, and call-by-value lambda calculus." |
@article{HLL07,
author = {F. Honsell and M. Lenisa and L. Liquori},
title = "A Framework for Defining Logical Frameworks",
journal = "Electronic Notes in Theoretical Computer Science",
volume = "172",
number = "",
pages = "399 - 436",
year = "2007",
note = "Computation, Meaning, and Logic: Articles dedicated to Gordon Plotkin",
issn = "1571-0661",
doi = "DOI: 10.1016/j.entcs.2007.02.014",
url = "http://www.sciencedirect.com/science/article/B75H1-4N7RX2N-G/2/7c4694b4f44f7479705fd7df4e5a6ba0",
PDF = {http://www-sop.inria.fr/mascotte/Luigi.Liquori/PAPERS/plotkin-feist-07.pdf},
abstract = " In this paper, we introduce a General Logical Framework, called GLF, for defining Logical Frameworks, based on dependent types, in the style of the well known Edinburgh Logical Framework LF. The framework GLF features a generalized form of lambda abstraction where [beta]-reductions fire provided the argument satisfies a logical predicate and may produce an n-ary substitution. The type system keeps track of when reductions have yet to fire. The framework GLF subsumes, by simple instantiation, LF as well as a large class of generalized constrained-based lambda calculi, ranging from well known restricted lambda calculi, such as Plotkin's call-by-value lambda calculus, to lambda calculi with patterns. But it suggests also a wide spectrum of new calculi which have intriguing potential as Logical Frameworks. We investigate the metatheoretical properties of the calculus underpinning GLF and illustrate its expressive power. In particular, we focus on two interesting instantiations of GLF. The first is the Pattern Logical Framework (PLF), where applications fire via pattern-matching in the style of Cirstea, Kirchner, and Liquori. The second is the Closed Logical Framework (CLF) which features, besides standard [beta]-reduction, also a reduction which fires only if the argument is a closed term. For both these instantiations of GLF we discuss standard metaproperties, such as subject reduction, confluence and strong normalization. The GLF framework is particularly suitable, as a metalanguage, for encoding rewriting logics and logical systems, where rules require proof terms to have special syntactic constraints, e.g. logics with rules of proof, in addition to rules of derivations, such as, e.g., modal logic, and call-by-value lambda calculus.",
sorte = "rev-int",
}
-
L. Liquori and S. Ronchi Della Rocca.
Intersection Typed System it à la Church.
IC, Journal of Information and Computation,
205(9):1371--1386,
September 2007.
[WWW
] [PDF
]
@ARTICLE{LiRo07,
author = {L. Liquori and S. {Ronchi Della Rocca}},
title = {Intersection Typed System {\it \`a la} {C}hurch},
journal = {IC, Journal of Information and Computation},
year = {2007},
volume = {205},
pages = {1371--1386},
number = {9},
month = sep,
pdf = {http://www-sop.inria.fr/mascotte/Luigi.Liquori/PAPERS/ic-07.pdf},
url = {http://dx.doi.org/10.1016/j.ic.2007.03.005},
sorte = "rev-int",
}
-
O. Amini,
S. Pérennes,
and I. Sau.
Hardness and Approximation of Traffic Grooming.
In The 18th International Symposium on Algorithms and Computation (ISAAC 2007),
volume 4835 of Lecture Notes in Computer Science,
Sendai, Japan,
pages 561-573,
December 2007.
Springer-Verlag.
[WWW
] [PDF
]
| Abstract: |
|
Traffic grooming is a central problem in optical networks. It refers to pack low rate signals into higher speed streams, in order to improve bandwidth utilization and reduce network cost. In WDM networks, the most accepted criterion is to minimize the number of electronic terminations, namely the number of SONET Add-Drop Multiplexers (ADMs). In this article we focus on ring and path topologies. On the one hand, we provide the first inapproximability result for \textsc{Traffic Grooming} for fixed values of the grooming factor $g$, answering affirmatively the conjecture of Chow and Lin (\emph{Networks, 44:194-202, 2004}). More precisely, we prove that \textsc{Ring Traffic Grooming} for fixed $g\geq 1$ and \textsc{Path Traffic Grooming} for fixed $g\geq 2$ are \textsc{APX}-complete. That is, they do not accept a PTAS unless $\textsc{P}=\textsc{NP}$. Both results rely on the fact that finding the maximum number of edge-disjoint triangles in a graph (and more generally cycles of length $2g+1$ in a graph of girth $2g+1$) is \textsc{APX}-complete. On the other hand, we provide a polynomial-time approximation algorithm for \textsc{Ring} and \textsc{Path Traffic Grooming}, based on a greedy cover algorithm, with an approximation ratio independent of $g$. Namely, the approximation guarantee is $\mathcal{O}(n^{1/3} \log2 n)$ for any $g \geq 1$, $n$ being the size of the network. This is useful in practical applications, since in backbone networks the grooming factor is usually greater than the network size. As far as we know, this is the first approximation algorithm with this property. Finally, we improve this approximation ratio under some extra assumptions about the request graph. |
@InProceedings{APS07c,
author = {O. Amini and S. P\'erennes and I. Sau},
title = {Hardness and Approximation of Traffic Grooming},
booktitle = {The 18th International Symposium on Algorithms and Computation (ISAAC 2007)},
year = {2007},
address = {Sendai, Japan},
month= dec,
publisher= { Springer-Verlag },
series= {Lecture Notes in Computer Science},
volume= { 4835 },
pages = {561-573},
url={http://www.nishizeki.ecei.tohoku.ac.jp/isaac07/},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/APS07b.pdf},
abstract = {Traffic grooming is a central problem in optical networks. It refers to pack low rate signals into higher speed streams, in order to improve bandwidth utilization and reduce network cost. In WDM networks, the most accepted criterion is to minimize the number of electronic terminations, namely the number of SONET Add-Drop Multiplexers (ADMs). In this article we focus on ring and path topologies. On the one hand, we provide the first inapproximability result for \textsc{Traffic Grooming} for fixed values of the grooming factor $g$, answering affirmatively the conjecture of Chow and Lin (\emph{Networks, 44:194-202, 2004}). More precisely, we prove that \textsc{Ring Traffic Grooming} for fixed $g\geq 1$ and \textsc{Path Traffic Grooming} for fixed $g\geq 2$ are \textsc{APX}-complete. That is, they do not accept a PTAS unless $\textsc{P}=\textsc{NP}$. Both results rely on the fact that finding the maximum number of edge-disjoint triangles in a graph (and more generally cycles of length $2g+1$ in a graph of girth $2g+1$) is \textsc{APX}-complete. On the other hand, we provide a polynomial-time approximation algorithm for \textsc{Ring} and \textsc{Path Traffic Grooming}, based on a greedy cover algorithm, with an approximation ratio independent of $g$. Namely, the approximation guarantee is $\mathcal{O}(n^{1/3} \log2 n)$ for any $g \geq 1$, $n$ being the size of the network. This is useful in practical applications, since in backbone networks the grooming factor is usually greater than the network size. As far as we know, this is the first approximation algorithm with this property. Finally, we improve this approximation ratio under some extra assumptions about the request graph.},
sorte = "conf-int"
}
-
O. Amini,
S. Pérennes,
and I. Sau.
Hardness of Approximating the Traffic Grooming.
In Neuvièmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'07),
Ile d'Oléron, France,
pages 45-48,
May 2007.
[WWW
] [PDF
]
| Abstract: |
|
Le groupage est un problème central dans l'étude des réseaux optiques. Dans cet article, on propose le premier résultat d'inapproximabilité pour le problème du groupage, en affirmant la conjecture de Chow et Lin (2004, Networks, 44, 194-202), selon laquelle le groupage est APX-complet. On étudie aussi une version amortie du problème de sous-graphe le plus dense dans un graphe donné: trouver le sous-graphe de taille minimum ayant le degré minimum au moins d, d>=3. On démontre que ce dernier n'a pas d'approximation à un facteur constant. |
@inproceedings{APS07a,
author = {O. Amini and S. P\'erennes and I. Sau},
title = {Hardness of Approximating the Traffic Grooming},
booktitle={Neuvi\`emes Rencontres Francophones sur les Aspects Algorithmiques des T\'el\'ecommunications (AlgoTel'07)},
pages = {45-48},
address={Ile d'Ol\'eron, France},
month=may,
year={2007},
URL={http://algotel2007.labri.fr/},
pdf={http://hal.inria.fr/action/open_file.php?url=http://hal.inria.fr/docs/00/17/69/60/PDF/59-APS-Algotel.pdf&docid=176960},
abstract={Le groupage est un problème central dans l'étude des réseaux optiques. Dans cet article, on propose le premier résultat d'inapproximabilité pour le problème du groupage, en affirmant la conjecture de Chow et Lin (2004, Networks, 44, 194-202), selon laquelle le groupage est APX-complet. On étudie aussi une version amortie du problème de sous-graphe le plus dense dans un graphe donné: trouver le sous-graphe de taille minimum ayant le degré minimum au moins d, d>=3. On démontre que ce dernier n'a pas d'approximation à un facteur constant.},
sorte = "conf-nat"
}
-
O. Amini and B. Reed.
List Colouring Constants of Triangle Free Graphs.
In IV Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS 07),
Puerto Varas, Chile,
pages 6p,
November 2007.
[WWW
] [PDF
]
| Abstract: |
|
In this paper we prove a result about vertex list colourings which in particular shows that a conjecture of the second author (1999, Journal of Graph Theory 31, 149-153) is true for triangle free graphs of large maximum degree. There exists a constant K such that the following holds: Given a graph G and a list assignment L to vertices of G, assigning a list of available colours L(v) to each vertex $v\in V(G)$, such that $|L(v)| = K\Delta/\log(\Delta)$ , then there exists a proper list colouring of vertices of G provided that for each colour c, the graph induced by all vertices v with c â L(v) is triangle free and has maximum degree at most \Delta. |
@InProceedings{AmRe07,
author = {O. Amini and B. Reed},
title = {List Colouring Constants of Triangle Free Graphs},
booktitle = {IV Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS 07)},
pages = {6p},
year = {2007},
address = {Puerto Varas, Chile},
month = nov,
url={http://www.dii.uchile.cl/~lagos07/},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/AmRe07.pdf},
abstract = {In this paper we prove a result about vertex list colourings which in particular shows that a conjecture of the second author (1999, Journal of Graph Theory 31, 149-153) is true for triangle free graphs of large maximum degree. There exists a constant K such that the following holds: Given a graph G and a list assignment L to vertices of G, assigning a list of available colours L(v) to each vertex $v\in V(G)$, such that $|L(v)| = K\Delta/\log(\Delta)$ , then there exists a proper list colouring of vertices of G provided that for each colour c, the graph induced by all vertices v with c â L(v) is triangle free and has maximum degree at most \Delta.},
sorte = "conf-int"
}
-
J. Araujo and C. Linhares Sales.
Teorema de Hajós para Coloração Ponderada.
In XXXIX Simpósio Brasileiro de Pesquisa Operacional,
Fortaleza, Brazil,
pages 5p,
August 2007.
[PDF
]
| Abstract: |
|
The vertex coloring problem is one of the most investigated problems in graph theory because of it models several important practical problems and because of its inherent difficulty: it is NP-hard to determine the chromatic number of a graph. The Theorem of Haj´os [Haj´os, 1961] shows a necessary and sufficient condition to a graph have chromatic number at least k: the graph must contain a k-constructible subgraph. A graph is k-constructible if it can be obtained from a complete graph by successively applying a set of well-defined operations. In this article, we prove that the weighted coloring problem [Guan and Zhu, 1997] admits a version of the Haj´osâ Theorem and so we show a necessary and sufficient condition to a weighted graph G have weighted chromatic number at least k, for any integer k. |
@InProceedings{ArLi07,
author = {J. Araujo and C. {Linhares Sales}},
title = {Teorema de Haj\'os para Colora\c c\~ao Ponderada},
booktitle = {XXXIX Simp\'osio Brasileiro de Pesquisa Operacional},
OPTcrossref = {},
OPTkey = {},
pages = {5p},
year = {2007},
OPTeditor = {},
OPTvolume = {XXXX},
OPTnumber = {XXXX},
series = {},
address = {Fortaleza, Brazil},
month = {August},
OPTorganization = {},
publisher = {},
OPTannote = {},
abstract = {The vertex coloring problem is one of the most investigated problems in graph theory because of it models several important practical problems and because of its inherent difficulty: it is NP-hard to determine the chromatic number of a graph. The Theorem of Haj´os [Haj´os, 1961] shows a necessary and sufficient condition to a graph have chromatic number at least k: the graph must contain a k-constructible subgraph. A graph is k-constructible if it can be obtained from a complete graph by successively applying a set of well-defined operations. In this article, we prove that the weighted coloring problem [Guan and Zhu, 1997] admits a version of the Haj´osâ Theorem and so we show a necessary and sufficient condition to a weighted graph G have weighted chromatic number at least k, for any integer k. },
OPTurl = {},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/AL07.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays={BR},
sorte = "conf-nat"
}
-
N. Ben Ali,
J. Moulierac,
B. Belghith,
and M. Molnár.
mQMA: multi-constrained QoS Multicast Aggregation.
In IEEE Global Telecommunications Conference (IEEE GLOBECOM 2007),
Washington DC, USA,
pages 5p,
November 2007.
[PDF
]
| Abstract: |
|
Traditional IP Multicast has been proposed in order to manage group communications over the Internet in a bandwidth efficient manner. Although this proposition has been well studied, there are still some problems for its deployment. In this paper, we propose a new algorithm mQMA that deals with two important problems of traditional IP multicast, i.e., multicast forwarding state scalability and multi-constrained QoS routing. The algorithm mQMA builds few trees and maintains few forwarding states for the groups thanks to the technique of multicast tree aggregation, which allows several groups to share the same delivery tree. Moreover, the algorithm mQMA builds trees satisfying multiple QoS constraints. We show, trough extensive simulations, that mQMA leverages the same QoS performances as Mamcra which is the main multi-constrained multicast routing algorithm. Moreover, mQMA reduces dramatically the number of trees to be maintained. |
@inproceedings{BMBM07,
author = {N. {Ben Ali} and J. Moulierac and B. Belghith and M. Moln\'ar},
title = {{mQMA: multi-constrained QoS Multicast Aggregation}},
booktitle = {IEEE Global Telecommunications Conference (IEEE GLOBECOM 2007)},
pages = {5p},
year = {2007},
address = {Washington DC, USA},
month = nov,
PDF={ftp://ftp-sop.inria.fr/mascotte/personnel/Joanna.Moulierac/pdf/benali07mqma.pdf},
ABSTRACT = {Traditional IP Multicast has been proposed in order to manage group communications over the Internet in a bandwidth efficient manner. Although this proposition has been well studied, there are still some problems for its deployment. In this paper, we propose a new algorithm mQMA that deals with two important problems of traditional IP multicast, i.e., multicast forwarding state scalability and multi-constrained QoS routing. The algorithm mQMA builds few trees and maintains few forwarding states for the groups thanks to the technique of multicast tree aggregation, which allows several groups to share the same delivery tree. Moreover, the algorithm mQMA builds trees satisfying multiple QoS constraints. We show, trough extensive simulations, that mQMA leverages the same QoS performances as Mamcra which is the main multi-constrained multicast routing algorithm. Moreover, mQMA reduces dramatically the number of trees to be maintained.},
sorte = "conf-int",
}
-
J-C. Bermond and M. Cosnard.
Minimum number of wavelengths equals load in a DAG without internal cycle.
In Parallel and Distributed Processing Symposium, 2007. IPDPS 2007. IEEE International,
Long Beach, CA, U.S.A.,
pages 1-10,
March 2007.
[PDF
]
@inproceedings{BeCo07,
author = {J-C. Bermond and M. Cosnard },
title = { Minimum number of wavelengths equals load in a DAG without internal cycle},
booktitle = {Parallel and Distributed Processing Symposium, 2007. IPDPS 2007. IEEE International},
pages = {1-10},
year = {2007},
month = mar,
address = {Long Beach, CA, U.S.A.},
PDF={http://www-sop.inria.fr/members/Jean-Claude.Bermond/PUBLIS/BC07.pdf},
sorte = "conf-int"
}
-
J-C. Bermond,
F. Giroire,
and S. Pérennes.
Design of Minimal Fault Tolerant On-Board Networks : Practical constructions.
In 14th International Colloquium on Structural Information and Communication Complexity (SIROCCO 07),
volume 4474 of Lecture Notes in Computer Sciences,
Castiglioncello, Italy,
pages 261-273,
June 2007.
[PDF
]
@InProceedings{BGP07,
author = {J-C. Bermond and F. Giroire and S. P\'erennes },
title = {Design of Minimal Fault Tolerant On-Board Networks : Practical constructions},
booktitle = {14th International Colloquium on Structural Information and Communication Complexity (SIROCCO 07)},
OPTcrossref = {},
OPTkey = {},
pages = {261-273},
year = {2007},
OPTeditor = {},
volume = {4474},
OPTnumber = {},
series = {Lecture Notes in Computer Sciences},
address = {Castiglioncello, Italy},
month = jun,
OPTorganization = {},
publisher = {},
PDF={http://www-sop.inria.fr/members/Jean-Claude.Bermond/PUBLIS/BGP07.pdf},
sorte = "conf-int"
}
-
J-C. Bermond,
F. Havet,
F. Huc,
and C. Linhares-Sales.
Allocation de fréquences et coloration impropre des graphes hexagonaux pondérés.
In Neuvièmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'07),
Ile d'Oléron, France,
pages 53-56,
May 2007.
[WWW
] [PDF
]
| Abstract: |
|
Motiv\'es par un probl\`eme d'allocation de fr\'equences, nous \'etudions la coloration impropre des graphes pond\'er\'es et plus particuli\`erement des graphes hexagonaux pond\'er\'es. Nous donnons des algorithmes d'approximation pour trouver de telles colorations. |
@inproceedings{BHHL07,
author = {J-C. Bermond and F. Havet and F. Huc and C. {Linhares-Sales}},
title = {Allocation de fr\'equences et coloration impropre des graphes hexagonaux pond\'er\'es},
booktitle={Neuvi\`emes Rencontres Francophones sur les Aspects Algorithmiques des T\'el\'ecommunications (AlgoTel'07)},
address={Ile d'Ol\'eron, France},
month=may,
pages = {53-56},
year={2007},
URL={http://algotel2007.labri.fr/},
PDF={ftp://ftp-sop.inria.fr/mascotte/Publications/BHH+07.pdf},
abstract = {Motiv\'es par un probl\`eme d'allocation de fr\'equences, nous \'etudions la coloration impropre des graphes pond\'er\'es et plus particuli\`erement des graphes hexagonaux pond\'er\'es. Nous donnons des algorithmes d'approximation pour trouver de telles colorations.},
sorte = "conf-nat"
}
-
S. Bessy,
N. Lichiardopol,
and J.-S. Sereni.
Two proofs of Bermond-Thomassen conjecture for regular tournaments.
In Proceedings of the sixth Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications,
volume 28 of Electronic Notes in Discrete Mathematics,
pages 47--53,
2007.
Elsevier.
[WWW
] [PDF
]
@InProceedings{BLS07b,
author = {S. Bessy and N. Lichiardopol and J.-S. Sereni},
title = {Two proofs of {B}ermond-{T}homassen conjecture for regular tournaments},
booktitle = {Proceedings of the sixth Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications},
publisher={Elsevier},
series={Electronic Notes in Discrete Mathematics},
volume={28},
pages = {47--53},
year = {2007},
URL = {http://kam.mff.cuni.cz/~cs06/},
PDF={http://www.sciencedirect.com/science?_ob=MImg&_imagekey=B75GV-4N5M9FJ-8-1&_cdi=13104&_user=4895301&_orig=browse&_coverDate=030.000000010.0000002007&_sk=999719999&view=c&wchp=dGLbVtz-zSkzk&md5=e44f5e8def6ba8f2a790b29f6bb262e6&ie=/sdarticle.pdf},
sorte = "conf-int",
}
-
E. Birmele,
J. A. Bondy,
and B. Reed.
Brambles, Prisms and Grids.
In Proceedings of a Conference in Memory of Claude Berge, Graph Theory in Paris,
Basel,
pages 37-44,
2007.
Birkhauser.
@INPROCEEDINGS{BBR07a,
author = "E. Birmele and J. A. Bondy and B. Reed",
title = "Brambles, Prisms and Grids",
booktitle = "Proceedings of a Conference in Memory of Claude Berge, Graph Theory in Paris",
pages = "37-44",
address = "Basel",
publisher = "Birkhauser",
year = 2007,
sorte = "conf-int",
}
-
R. Chand,
L. Liquori,
and M. Cosnard.
Improving Resource Discovery in the Arigatoni Overlay Network.
In 20th International Conference on Architecture of Computing Systems (ARCS 2007),
volume 4415 of Lecture Notes in Computer Science,
Zurich, Switzerland,
pages 98--111,
2007.
Springer.
[PDF
]
@inproceedings{CLC07,
author = {R. Chand and L. Liquori and M. Cosnard},
title = {Improving Resource Discovery in the Arigatoni Overlay Network},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
booktitle = {20th International Conference on Architecture of Computing Systems (ARCS 2007)},
volume = {4415},
year = {2007},
pages = {98--111},
address = {Zurich, Switzerland},
PDF = {http://www-sop.inria.fr/mascotte/Luigi.Liquori/PAPERS/arcs-07.pdf},
sorte = "conf-int",
}
-
A. Chattopadhyay and B. Reed.
Properly 2-Colouring Linear Hypergraphs.
In 11th Intl. Workshop on Randomization and Computation (RANDOM 2007),
volume 4627 of Lecture Notes in Computer Science,
Princeton University, NJ, USA,
pages 395-408,
2007.
Springer.
[PDF
]
@inproceedings{ChRe07,
author = {A. Chattopadhyay and B. Reed},
title = {Properly 2-Colouring Linear Hypergraphs},
booktitle = {11th Intl. Workshop on Randomization and Computation (RANDOM 2007)},
address = {Princeton University, NJ, USA},
year = {2007},
pages = {395-408},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
volume = {4627},
PDF = {ftp://ftp-sop.inria.fr/mascotte/Publications/ChRe07.pdf},
sorte = "conf-int",
}
-
M. Cosnard,
L. Liquori,
and R. Chand.
Virtual Organizations in Arigatoni.
In DCM, International Workshop on Developpment in Computational Models,
volume 171 of Electronique Notes in Theoretical Computer Science,
pages 55--75,
2007.
[WWW
] [PDF
]
@INPROCEEDINGS{CLC07b,
author = {M. Cosnard and L. Liquori and R. Chand},
title = {Virtual Organizations in Arigatoni},
booktitle = {DCM, International Workshop on Developpment in Computational Models},
year = {2007},
volume = {171},
OPTnumber = {3},
series = {Electronique Notes in Theoretical Computer Science},
pages = {55--75},
url = {http://dx.doi.org/10.1016/j.entcs.2006.11.035},
pdf = {http://www-sop.inria.fr/mascotte/Luigi.Liquori/PAPERS/dcm-06.pdf},
sorte = "conf-int",
}
-
A. da Silva,
A. da Silva,
and C. Linhares-Sales.
Largura em Árvore de Grafos Planares Livres de Ciclos Pares Induzidos.
In XXXIX Congresso da Sociedade Brasileira de Pesquisa Operacional (SBPO 2007),
Fortaleza, Brazil,
August 2007.
[WWW
]
@inproceedings{SSL07,
author = {A. {da Silva} and A. {da Silva} and C. {Linhares-Sales}},
title = {Largura em \'Arvore de Grafos Planares Livres de Ciclos Pares Induzidos},
booktitle={XXXIX Congresso da Sociedade Brasileira de Pesquisa Operacional (SBPO 2007)},
address={Fortaleza, Brazil},
month=aug,
year={2007},
URL={http://www.sobrapo.org.br/simposios/XXXIX/indexxxxix.htm},
sorte = "conf-nat",
}
-
O. Dalle.
Component-based Discrete Event Simulation Using the Fractal Component Model.
In AI, Simulation and Planning in High Autonomy Systems (AIS)-Conceptual Modeling and Simulation (CMS) Joint Conference,
Buenos Aires, AR,
pages 213--218,
February 2007.
[PDF
]
@InProceedings{Dal07a,
author = {O. Dalle},
title = {Component-based Discrete Event Simulation Using the Fractal Component Model},
booktitle = {{AI}, Simulation and Planning in High Autonomy Systems (AIS)-Conceptual Modeling and Simulation (CMS) Joint Conference },
OPTcrossref = {},
OPTkey = {},
pages = {213--218},
year = {2007},
OPTeditor = {},
OPTvolume = {},
OPTnumber = {},
OPTseries = {},
address = {Buenos Aires, AR},
month = feb,
OPTorganization = {},
OPTpublisher = {},
OPTnote = {},
OPTannote = {},
PDF = {ftp://ftp-sop.inria.fr/mascotte/Publications/Dal07a.pdf},
sorte = "conf-int"
}
-
O. Dalle.
The OSA Project: an Example of Component Based Software Engineering Techniques Applied to Simulation.
In Proc. of the Summer Computer Simulation Conference (SCSC'07),
San Diego, CA, USA,
pages 1155--1162,
July 2007.
Note: Invited paper.
[PDF
]
@InProceedings{Dal07b,
OPTkey = {},
author = {O. Dalle},
title = {The {OSA} {P}roject: an {E}xample of {C}omponent {B}ased {S}oftware {E}ngineering {T}echniques {A}pplied to {S}imulation},
booktitle = {Proc. of the Summer Computer Simulation Conference (SCSC'07)},
pages = {1155--1162},
address = {San Diego, CA, USA},
month = jul,
year = {2007},
note = {Invited paper},
PDF = {ftp://ftp-sop.inria.fr/mascotte/Publications/Dal07b.pdf},
OPTannote = {},
sorte = "conf-int"
}
-
O. Dalle and C. Mrabet.
An Instrumentation Framework for component-based simulations based on the Separation of Concerns paradigm.
In Proc. of 6th EUROSIM Congress (EUROSIM'2007),
Ljubljana, Slovenia,
pages 10p,
September 2007.
[PDF
]
@InProceedings{DaMr07,
author = {O. Dalle and C. Mrabet},
title = {An {I}nstrumentation {F}ramework for component-based simulations based on the {S}eparation of {C}oncerns paradigm},
booktitle = {Proc. of 6th EUROSIM Congress (EUROSIM'2007)},
OPTcrossref = {},
OPTkey = {},
pages = {10p},
year = {2007},
OPTeditor = {},
OPTvolume = {},
OPTnumber = {},
OPTseries = {},
address = {Ljubljana, Slovenia},
month = sep,
OPTorganization = {},
OPTpublisher = {},
PDF = {ftp://ftp-sop.inria.fr/mascotte/Publications/DaMr07.pdf},
OPTannote = {},
sorte = "conf-int"
}
-
O. Dalle and G. Wainer.
An Open Issue on Applying Sharing Modeling Patterns in DEVS.
In Proc. of the DEVS Workshop of the Summer Computer Simulation Conference (SCSC'07),
San Diego, CA,
July 2007.
Note: Short paper.
[PDF
]
@InProceedings{DaWa07,
author = {O. Dalle and G. Wainer},
title = {An Open Issue on Applying Sharing Modeling Patterns in DEVS},
booktitle = {Proc. of the DEVS Workshop of the Summer Computer Simulation Conference (SCSC'07)},
OPTcrossref = {},
OPTkey = {},
OPTpages = {},
year = {2007},
OPTeditor = {},
OPTvolume = {},
OPTnumber = {},
OPTseries = {},
address = {San Diego, CA},
month = jul,
OPTorganization = {},
OPTpublisher = {},
note = {Short paper},
OPTannote = {},
PDF = {ftp://ftp-sop.inria.fr/mascotte/Publications/DaWa07.pdf},
sorte = "conf-int"
}
-
G. Danoy,
P. Bouvry,
and L. Hogie.
Coevolutionary Genetic Algorithms for Ad Hoc Injection Networks Design Optimization.
In Proceedings of the IEEE Congress on Evolutionary Computation - CEC,
Singapore,
pages 8p,
September 2007.
IEEE.
[WWW
] [PDF
]
| Abstract: |
|
When considering realistic mobility patterns, nodes in mobile ad hoc networks move in such a way that the networks most often get divided in a set of disjoint partitions. This presence of partitions is an obstacle to communication within these networks. Ad hoc networks are generally based on technologies allowing nodes in a geographical neighborhood to communicate for free, in a P2P manner. These technologies include IEEE802.11 (Wi-Fi), Bluetooth, etc. In most cases a communication infrastructure is available. It can be a set of access point as well as GMS/UMTS network. The use of such an infrastructure is billed, but it permits distant nodes to get in communication, through what we call "bypass links". The objective of our work is to improve the network connectivity by defining a set of long distance connections. To do this we consider the number of bypass links, as well as the two properties that build on the "small-world" graph theory: the clustering coefficient, and the characteristic path length. A fitness function, used for genetic optimization, is processed out of these three metrics. In this paper we investigate the use of two Coevolutionary Genetic Algorithms (LCGA and CCGA) and compare their performance to a generational and a steadystate genetic algorithm (genGA and ssGA) for optimizing one instance of this topology control problem and present evidence of their capacity to solve it. |
@INPROCEEDINGS{DBH07,
OPTauthor = {Gr{\'e}goire Danoy and Pascal Bouvry and L. Hogie},
author = {G. Danoy and P. Bouvry and L. Hogie},
title = {Coevolutionary Genetic Algorithms for Ad Hoc Injection Networks Design Optimization},
booktitle = {Proceedings of the IEEE Congress on Evolutionary Computation - CEC},
pages = {8p},
year = {2007},
publisher = {IEEE},
address = {Singapore},
month = sep,
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/DBH07.pdf},
abstract = {When considering realistic mobility patterns, nodes in mobile ad hoc networks move in such a way that the networks most often get divided in a set of disjoint partitions. This presence of partitions is an obstacle to communication within these networks. Ad hoc networks are generally based on technologies allowing nodes in a geographical neighborhood to communicate for free, in a P2P manner. These technologies include IEEE802.11 (Wi-Fi), Bluetooth, etc. In most cases a communication infrastructure is available. It can be a set of access point as well as GMS/UMTS network. The use of such an infrastructure is billed, but it permits distant nodes to get in communication, through what we call "bypass links". The objective of our work is to improve the network connectivity by defining a set of long distance connections. To do this we consider the number of bypass links, as well as the two properties that build on the "small-world" graph theory: the clustering coefficient, and the characteristic path length. A fitness function, used for genetic optimization, is processed out of these three metrics. In this paper we investigate the use of two Coevolutionary Genetic Algorithms (LCGA and CCGA) and compare their performance to a generational and a steadystate genetic algorithm (genGA and ssGA) for optimizing one instance of this topology control problem and present evidence of their capacity to solve it.},
url = {http://www.google.fr/url?sa=t&source=web&ct=res&cd=1&ved=0CBcQFjAA&url=ftp0X1.2AB52P-885-16231083800624715025648228832155020226166892719138018421525037632987473280314397391192269858494702975413828793994344961730315854330232890054744206295222504730102436050490447205944018758853219057263022459675248963747430121648560444313413255982990181978237473570041841837066007183829415589688357099523473932288.0000000.000000ftp-sop.inria.fr0.000000mascotte0.000000Publications0.000000DBH07.pdf&ei=kR3oS56bE9D8_AaxkqDNBA&usg=AFQjCNEbq-NiZZVsEBA_5YSlnrlB_RbRAg},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
A. Ferreira,
A. Goldman,
and J. Monteiro.
On the evaluation of shortest journeys in dynamic networks.
In Proceedings of the 6th IEEE International Symposium on Network Computing and Applications,
Cambridge, MA, USA,
pages 3--10,
July 2007.
Note: Invited Paper.
[PDF
]
| Abstract: |
|
The assessment of routing protocols for wireless networks is a difficult task, because of the networksâ highly dynamic behavior and the absence of benchmarks. However, some of these networks, such as intermittent wireless sensors networks, periodic or cyclic networks, and low earth orbit (LEO) satellites systems, have more predictable dynamics, as the temporal variations in the network topology are somehow deterministic, which may make them easier to study. The graph theoretic model â the evolving graphs â was proposed to help capture the dynamic behavior of these networks, in view of the construction of least cost routing and other algorithms. Our recent experiments showed that evolving graphs have all the potentials to be an effective and powerful tool in the development of routing protocols for dynamic networks. In this paper, we evaluated the shortest journey evolving graph algorithm when used in a routing protocol for MANETs. We use the NS2 network simulator to compare this first implementation to the four well known protocols, namely AODV, DSR, DSDV, and OLSR. In this paper we present simulation results on the energy consumption of the nodes. We also included other EG protocol, namely EGForemost , in the experiments. |
@inproceedings{AGM07a,
author = { A. Ferreira and A. Goldman and J. Monteiro},
title = {On the evaluation of shortest journeys in dynamic networks},
booktitle = {Proceedings of the 6th {IEEE} International Symposium on Network Computing and Applications},
pages = {3--10},
month = jul,
year = {2007},
address = {Cambridge, MA, USA},
note = {Invited Paper},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/AGM07a.pdf},
abstract = {The assessment of routing protocols for wireless networks is a difficult task, because of the networksâ highly dynamic behavior and the absence of benchmarks. However, some of these networks, such as intermittent wireless sensors networks, periodic or cyclic networks, and low earth orbit (LEO) satellites systems, have more predictable dynamics, as the temporal variations in the network topology are somehow deterministic, which may make them easier to study. The graph theoretic model â the evolving graphs â was proposed to help capture the dynamic behavior of these networks, in view of the construction of least cost routing and other algorithms. Our recent experiments showed that evolving graphs have all the potentials to be an effective and powerful tool in the development of routing protocols for dynamic networks. In this paper, we evaluated the shortest journey evolving graph algorithm when used in a routing protocol for MANETs. We use the NS2 network simulator to compare this first implementation to the four well known protocols, namely AODV, DSR, DSDV, and OLSR. In this paper we present simulation results on the energy consumption of the nodes. We also included other EG protocol, namely EGForemost , in the experiments.},
sorte = "inv-conf"
}
-
A. Ferreira,
A. Goldman,
and J. Monteiro.
Using Evolving Graphs Foremost Journey to Evaluate Ad-Hoc Routing Protocols.
In Proceedings of 25th Brazilian Symposium on Computer Networks (SBRC'07),
Belem, Brazil,
pages 17--30,
June 2007.
[PDF
]
| Abstract: |
|
The performance evaluation of routing protocols for ad hoc networks is a difficult task. However, a graph theoretic model â the evolving graphs â was recently proposed to help capture the behavior of dynamic networks with fixed-schedule behavior. Our recent experiments showed that evolving graphs have all the potentials to be an effective and powerful tool in the development of routing protocols for dynamic networks. In this paper, we design a new con- gestion avoidance mechanism and a modified end-to-end delay metric in order to improve the evolving graph based routing protocol proposed previously. We use the NS2 network simulator to compare this new version to the three proto- cols provided by NS2, namely AODV, DSR and DSDV, and to OLSR, which is included in the experiments for the first time. |
@inproceedings{AGM07b,
author = {A. Ferreira and A. Goldman and J. Monteiro},
title = { Using Evolving Graphs Foremost Journey to Evaluate Ad-Hoc Routing Protocols},
booktitle = {Proceedings of 25th Brazilian Symposium on Computer Networks ({SBRC}'07)},
month = jun,
year = {2007},
pages = {17--30},
address = {Belem, Brazil},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/AGM07b.pdf},
abstract = {The performance evaluation of routing protocols for ad hoc networks is a difficult task. However, a graph theoretic model â the evolving graphs â was recently proposed to help capture the behavior of dynamic networks with fixed-schedule behavior. Our recent experiments showed that evolving graphs have all the potentials to be an effective and powerful tool in the development of routing protocols for dynamic networks. In this paper, we design a new con- gestion avoidance mechanism and a modified end-to-end delay metric in order to improve the evolving graph based routing protocol proposed previously. We use the NS2 network simulator to compare this new version to the three proto- cols provided by NS2, namely AODV, DSR and DSDV, and to OLSR, which is included in the experiments for the first time.},
sorte = "conf-nat"
}
-
E. Fusy and F. Giroire.
Estimating the number of active flows in a data stream over a sliding window.
In David Appelgate, editor,
Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithmics and Combinatorics,
pages 223-231,
2007.
SIAM Press.
Note: Proceedings of the New Orleans Conference.
[PDF
]
| Abstract: |
|
A new algorithm is introduced to estimate the number of distinct flows (or connections) in a data stream. The algorithm maintains an accurate estimate of the number of distinct flows over a sliding window. It is simple to implement, parallelizes optimally, and has a very good trade-off between auxiliary memory and accuracy of the estimate: a relative accuracy of order $1/\sqrt{m}$ requires essentially a memory of order $m\ln(n/m)$ words, where $n$ is an upper bound on the number of flows to be seen over the sliding window. For instance, a memory of only $64 kB$ is sufficient to maintain an estimate with accuracy of order $4$ percents for a stream with several million flows. The algorithm has been validated both by simulations and experimentations on real traffic. It proves very efficient to monitor traffic and detect attacks. |
@inproceedings{FuGi07,
author = {E. Fusy and F. Giroire},
title = {Estimating the number of active flows in a data stream over a sliding window},
booktitle = {Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithmics and Combinatorics},
year = {2007},
editor = {Appelgate, David},
publisher = {SIAM Press},
pages = {223-231},
note = {Proceedings of the New Orleans Conference},
pdf = {http://www-sop.inria.fr/members/Frederic.Giroire/publis/FuGi07.pdf},
abstract = {A new algorithm is introduced to estimate the number of distinct flows (or connections) in a data stream. The algorithm maintains an accurate estimate of the number of distinct flows over a sliding window. It is simple to implement, parallelizes optimally, and has a very good trade-off between auxiliary memory and accuracy of the estimate: a relative accuracy of order $1/\sqrt{m}$ requires essentially a memory of order $m\ln(n/m)$ words, where $n$ is an upper bound on the number of flows to be seen over the sliding window. For instance, a memory of only $64 kB$ is sufficient to maintain an estimate with accuracy of order $4$ percents for a stream with several million flows. The algorithm has been validated both by simulations and experimentations on real traffic. It proves very efficient to monitor traffic and detect attacks.},
}
-
J. Galtier.
Analysis and optimization of MAC with constant size congestion window for WLAN.
In The Second International Conference on Systems and Networks Communications (ICSNC'07),
Cap Esterel, French Riviera, France,
pages 6p,
August 2007.
[PDF
]
@inproceedings{Gal07a,
title = {Analysis and optimization of {MAC} with constant size congestion window for {WLAN}},
author = {J. Galtier},
booktitle = {The Second International Conference on Systems and Networks Communications (ICSNC'07)},
pages = {6p},
address = {Cap Esterel, French Riviera, France},
year = {2007},
month = aug,
PDF = {ftp://ftp-sop.inria.fr/mascotte/Publications/Gal07.pdf},
sorte = "conf-int"
}
-
C. Gomes and G. Huiban.
Multiobjective Analysis in Wireless Mesh Networks.
In International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS),
pages 103--108,
October 2007.
Bogazici University, Istanbul, Turkey,
IEEE.
[WWW
] [PDF
]
| Abstract: |
|
Wireless Mesh Networks is a scalable and cost-effective solution for next-generation wireless networking. In the present work, we consider the Round Weighting Problem (RWP). It solves a joint routing and scheduling problem to attend a given demand subjected to the multiaccess interferences. We proposed a multiobjective approach that deal with two objective functions. The first one is to minimize the load over the routers, it increases the security in case of failure and minimizes the cost with memory in each node. The second objective is to minimize the time of the communication. We aim to identify the Pareto frontier of the problem. The Column generation method was used to solve efficiently the test instances. We make experiments with some networks with different number of sinks. Our approach captures the trade-off generated by using these two conflicting objective functions. This relationship corresponds to a convex piecewise linear function. |
@InProceedings{GoHu07a,
author = {C. Gomes and G. Huiban},
title = {Multiobjective Analysis in Wireless Mesh Networks},
booktitle = {International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS)},
pages = {103--108},
year = {2007},
month = oct,
organization = {Bogazici University, Istanbul, Turkey},
publisher = {IEEE},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/GoHu07a.pdf},
url = {http://www.cmpe.boun.edu.tr/mascots07/},
abstract = {Wireless Mesh Networks is a scalable and cost-effective solution for next-generation wireless networking. In the present work, we consider the Round Weighting Problem (RWP). It solves a joint routing and scheduling problem to attend a given demand subjected to the multiaccess interferences. We proposed a multiobjective approach that deal with two objective functions. The first one is to minimize the load over the routers, it increases the security in case of failure and minimizes the cost with memory in each node. The second objective is to minimize the time of the communication. We aim to identify the Pareto frontier of the problem. The Column generation method was used to solve efficiently the test instances. We make experiments with some networks with different number of sinks. Our approach captures the trade-off generated by using these two conflicting objective functions. This relationship corresponds to a convex piecewise linear function.},
sorte = "conf-int"
}
-
C. Gomes,
C. Molle,
P. Reyes,
and H. Rivano.
Models for Optimal Wireless Mesh Network Design.
In The 22nd European Conference on Operational Research (EURO XXII),
Prague,
pages 1p,
July 2007.
| Abstract: |
|
Wireless Mesh Networks (WMNs) are cost-effective and provide an appealing answer to connectivity issues of ubiquituous computing. Unfortunately, wireless networks are known for strong waste of capacity when their size increase. Thus, a key challenges for network operators is to provide guaranteed quality of service. Maximizing network capacity requires to optimize jointly the Access Points (AP) placement, the routing and the link scheduling taking interferences into account. We present MILP models for computing an optimal 802.11a or 802.16 WMN design providing max-min bandwidth guaranty. |
@INPROCEEDINGS{GMRR07b,
author = {C. Gomes and C. Molle and P. Reyes and H. Rivano},
title = {Models for Optimal Wireless Mesh Network Design},
booktitle = {The 22nd European Conference on Operational Research (EURO XXII)},
pages = {1p},
year = {2007},
address = {Prague},
month = jul,
abstract = {Wireless Mesh Networks (WMNs) are cost-effective and provide an appealing answer to connectivity issues of ubiquituous computing. Unfortunately, wireless networks are known for strong waste of capacity when their size increase. Thus, a key challenges for network operators is to provide guaranteed quality of service. Maximizing network capacity requires to optimize jointly the Access Points (AP) placement, the routing and the link scheduling taking interferences into account. We present MILP models for computing an optimal 802.11a or 802.16 WMN design providing max-min bandwidth guaranty.},
sorte = "conf-sa"
}
-
C. Gomes,
C. Molle,
P. Reyes,
and H. Rivano.
Placement Optimal de points d'accès dans les réseaux radio maillés.
In Neuvièmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'07),
Ile d'Oléron, France,
pages 117-120,
May 2007.
[WWW
] [PDF
]
| Abstract: |
|
Cet article pr\'esente un mod\`ele lin\'eaire permettant de placer un nombre minimum de points d'acc\`es dans un r\'eseau radio maill\'e ({\em Wireless Mesh Network}). Connaissant la topologie du r\'eseau, le probl\`eme est de d\'eterminer le nombre minimum de points d'acc\`es reli\'es \`a Internet n\'ecessaires pour que la demande de chaque routeur soit satisfaite. Afin de prendre en compte les interf\'erences spatiales d\^ues \`a la technologie radio, le temps est d\'ecoup\'e en intervalles r\'eguliers au cours desquels un ensemble de liens n'interf\'erant pas deux \`a deux est d\'etermin\'e, ce qui engendre une limitation de la capacit\'e des liens en fonction de leur activation dans le temps. Le placement se fait ensuite de mani\`ere \`a assurer \`a chaque n\oe{}ud le d\'ebit d\'esir\'e en r\'egime permanent. |
@INPROCEEDINGS{GMRR07a,
author = {C. Gomes and C. Molle and P. Reyes and H. Rivano},
title = {Placement Optimal de points d'acc\`es dans les r\'eseaux radio maill\'es},
booktitle = {Neuvi\`emes Rencontres Francophones sur les Aspects Algorithmiques des T\'el\'ecommunications (AlgoTel'07)},
pages = {117-120},
year = {2007},
address = {Ile d'Ol\'eron, France},
month = may,
abstract = {Cet article pr\'esente un mod\`ele lin\'eaire permettant de placer un nombre minimum de points d'acc\`es dans un r\'eseau radio maill\'e ({\em Wireless Mesh Network}). Connaissant la topologie du r\'eseau, le probl\`eme est de d\'eterminer le nombre minimum de points d'acc\`es reli\'es \`a Internet n\'ecessaires pour que la demande de chaque routeur soit satisfaite. Afin de prendre en compte les interf\'erences spatiales d\^ues \`a la technologie radio, le temps est d\'ecoup\'e en intervalles r\'eguliers au cours desquels un ensemble de liens n'interf\'erant pas deux \`a deux est d\'etermin\'e, ce qui engendre une limitation de la capacit\'e des liens en fonction de leur activation dans le temps. Le placement se fait ensuite de mani\`ere \`a assurer \`a chaque n\oe{}ud le d\'ebit d\'esir\'e en r\'egime permanent.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/GMRR07.pdf},
url = {http://algotel2007.labri.fr/},
sorte = "conf-nat"
}
-
F. Havet,
J. van den Heuvel,
C. McDiarmid,
and B. Reed.
List colouring squares of planar graphs.
In European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2007),
volume 29 of Electronic Notes in Discrete Mathematics,
Sevilla, Spain,
pages 515-519,
September 2007.
[PDF
]
@InProceedings{HHMR07,
AUTHOR="F. Havet and J. {van den Heuvel} and C. McDiarmid and B. Reed",
TITLE="List colouring squares of planar graphs",
booktitle ="European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2007)",
PAGES = "515-519",
volume = {29},
series = {Electronic Notes in Discrete Mathematics},
year = "2007",
address = "Sevilla, Spain",
month = sep,
pdf={ftp://ftp-sop.inria.fr/mascotte/Publications/HH+07.pdf},
sorte = "conf-int",
}
-
G. Huiban and P. Datta.
Multi-Metrics Reconfiguration in Core WDM Networks.
In International Workshop on the Design of Reliable Communication Networks (DRCN),
La Rochelle, France,
pages 8p,
October 2007.
SEE.
[WWW
] [PDF
]
| Abstract: |
|
We consider the reconfiguration problem in multifiber WDM optical networks. In a network with evolving traffic, the virtual topology may not remain optimal, leading to degradation of network performance. However, adapting the virtual topology to the changing traffic may lead to service disruption. This optimization problem hence captures the trade-off between network performance and number of reconfigurations applied to the virtual topology. This trade-off is considered via a multi-metrics approach. The above problem is solved through a Mixed Integer Linear Programming (MILP) formulation with a multivariate objective function. However the problem is NP-hard and such an approach is unable to solve large problem instances in a reasonable time. Therefore we propose a simulated annealing (SA) based heuristic approach for solving problems of higher complexity. We compare the performance and the computation time of solving the MILP model and the heuristic approach considering different test instances. We can find near optimal solutions for instances of medium complexity using the MILP model. The SA scheme can be used as a heuristic to arrive at near optimal solutions when the run-time of the MILP becomes practically infeasible. It also appears that the trade-off's involved in the reconfiguration problem cannot be left aside, as a little flexibility with respect to one metric allows to drastically improve the quality of the solution with respect to other metrics. |
@InProceedings{HuDa07,
author = {G. Huiban and P. Datta},
title = {Multi-Metrics Reconfiguration in Core WDM Networks},
booktitle = {International Workshop on the Design of Reliable Communication Networks (DRCN)},
year = {2007},
pages = {8p},
month = oct,
publisher = {SEE},
address = {La Rochelle, France},
url = {http://www.drcn.org/drcn07/},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/HuDa07.pdf},
abstract = {We consider the reconfiguration problem in multifiber WDM optical networks. In a network with evolving traffic, the virtual topology may not remain optimal, leading to degradation of network performance. However, adapting the virtual topology to the changing traffic may lead to service disruption. This optimization problem hence captures the trade-off between network performance and number of reconfigurations applied to the virtual topology. This trade-off is considered via a multi-metrics approach. The above problem is solved through a Mixed Integer Linear Programming (MILP) formulation with a multivariate objective function. However the problem is NP-hard and such an approach is unable to solve large problem instances in a reasonable time. Therefore we propose a simulated annealing (SA) based heuristic approach for solving problems of higher complexity. We compare the performance and the computation time of solving the MILP model and the heuristic approach considering different test instances. We can find near optimal solutions for instances of medium complexity using the MILP model. The SA scheme can be used as a heuristic to arrive at near optimal solutions when the run-time of the MILP becomes practically infeasible. It also appears that the trade-off's involved in the reconfiguration problem cannot be left aside, as a little flexibility with respect to one metric allows to drastically improve the quality of the solution with respect to other metrics.},
sorte = "conf-int",
}
-
D. Ilcinkas,
N. Nisse,
and D. Soguet.
The Cost of Monotonicity in Distributed Graph Searching.
In OPODIS,
volume 4878 of Lecture Notes in Computer Science,
Guadeloupe, France,
pages 415-428,
December 2007.
Springer.
[WWW
] [PDF
]
| Abstract: |
|
Blin {\it et al.} (2006) proposed a distributed protocol that ena\-bles the smallest number of searchers to clear any unknown asynchronous graph in a decentralized manner. {\it Unknown} means that the searchers are provided no {\it a priori} information about the graph. However, the strategy that is actually performed lacks of an important property, namely the monotonicity. That is, the clear part of the graph can decrease at some steps of the execution of the protocol. As a consequence, the protocol of Blin {\it et al.} is executed in exponential time. Nisse and Soguet (2007) proved that, in order to ensure the smallest number of searchers to clear any $n$-node graph in a monotone way, it is necessary and sufficient to provide $\Theta(n \log n)$ bits of information to the searchers. This paper deals with the smallest number of searchers that are necessary and sufficient to monotoneously clear any unknown graph in a decentralized manner. The distributed graph searching problem considers a team of searchers that is aiming at clearing any connected contaminated graph. The clearing of the graph is required to be {\it connected}, i.e., the clear part of the graph must remain permanently connected, and {\it monotone}, i.e., the clear part of the graph only grows. The {\it search number} $\mcs(G)$ of a graph $G$ is the smallest number of searchers necessary to clear $G$ in a monotone connected way in centralized settings. We prove that $\Theta(\frac{n}{\log n}\, \mcs(G))$ searchers are necessary and sufficient to clear any unknown $n$-node graph $G$ in a monotone connected way, in decentralized settings. More precisely, we prove that, no distributed protocol using less than $\Omega(\frac{n}{\log n}\, \mcs(G))$ searchers can clear any unknown synchronous $n$-node graph $G$ in a monotone connected way. Moreover, we propose a distributed protocol that allows $O(\frac{n}{\log n}\, \mcs(G))$ searchers to clear any unknown asynchronous $n$-node graph $G$ in a monotone connected way. |
@inproceedings{INS07,
sorte = "conf-int",
author = {D. Ilcinkas and N. Nisse and D. Soguet},
title = {The Cost of Monotonicity in Distributed Graph Searching},
booktitle = {Proceedings of the 11th International Conference on Principles of Distributed Systems (OPODIS)},
year = {2007},
month = dec,
pages = {415-428},
booktitle = {OPODIS},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
volume = {4878},
address = {Guadeloupe, France},
abstract = {Blin {\it et al.} (2006) proposed a distributed protocol that ena\-bles the smallest number of searchers to clear any unknown asynchronous graph in a decentralized manner. {\it Unknown} means that the searchers are provided no {\it a priori} information about the graph. However, the strategy that is actually performed lacks of an important property, namely the monotonicity. That is, the clear part of the graph can decrease at some steps of the execution of the protocol. As a consequence, the protocol of Blin {\it et al.} is executed in exponential time. Nisse and Soguet (2007) proved that, in order to ensure the smallest number of searchers to clear any $n$-node graph in a monotone way, it is necessary and sufficient to provide $\Theta(n \log n)$ bits of information to the searchers. This paper deals with the smallest number of searchers that are necessary and sufficient to monotoneously clear any unknown graph in a decentralized manner. The distributed graph searching problem considers a team of searchers that is aiming at clearing any connected contaminated graph. The clearing of the graph is required to be {\it connected}, i.e., the clear part of the graph must remain permanently connected, and {\it monotone}, i.e., the clear part of the graph only grows. The {\it search number} $\mcs(G)$ of a graph $G$ is the smallest number of searchers necessary to clear $G$ in a monotone connected way in centralized settings. We prove that $\Theta(\frac{n}{\log n}\, \mcs(G))$ searchers are necessary and sufficient to clear any unknown $n$-node graph $G$ in a monotone connected way, in decentralized settings. More precisely, we prove that, no distributed protocol using less than $\Omega(\frac{n}{\log n}\, \mcs(G))$ searchers can clear any unknown synchronous $n$-node graph $G$ in a monotone connected way. Moreover, we propose a distributed protocol that allows $O(\frac{n}{\log n}\, \mcs(G))$ searchers to clear any unknown asynchronous $n$-node graph $G$ in a monotone connected way.},
url = {http://www.informatik.uni-trier.de/~ley/db/conf/opodis/opodis2007.shtml},
pdf = {http://www-sop.inria.fr/members/Nicolas.Nisse/publications/Opodis07.ps}
}
-
K. Kawarabayashi and B. Reed.
Computing crossing number in linear time..
In 39th ACM Symposium on Theory of Computing (STOC 2007),
San Diego, CA, USA,
pages 382-390,
June 2007.
@inproceedings{KaRe07,
author = {K. Kawarabayashi and B. Reed},
title = {Computing crossing number in linear time.},
booktitle = {39th ACM Symposium on Theory of Computing (STOC 2007)},
address = {San Diego, CA, USA},
month = jun,
year = {2007},
pages = {382-390},
sorte = "conf-int",
}
-
A. King and B. Reed.
Asymptotics of the chromatic number for quasi-line graphs.
In European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2007),
volume 29 of Electronic Notes in Discrete Mathematics,
Sevilla, Spain,
pages 327-331,
September 2007.
@InProceedings{KiRe07,
AUTHOR="A. King and B. Reed",
TITLE="Asymptotics of the chromatic number for quasi-line graphs",
booktitle ="European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2007)",
volume = {29},
pages = {327-331},
series = {Electronic Notes in Discrete Mathematics},
year = "2007",
address = "Sevilla, Spain",
month = sep,
sorte = "conf-int",
}
-
L. Liquori and M. Cosnard.
Logical Networks: Towards Foundations for Programmable Overlay Networks and Overlay Computing Systems.
In 3rd Symposium on Trustworthy Global Computing (TGC 2007),
volume 4912 of Lecture Notes in Computer Science,
Sophia Antipolis, France,
pages 90-107,
November 2007.
Springer.
[PDF
]
@inproceedings{LiCo07b,
author = {L. Liquori and M. Cosnard},
title = {{Logical Networks: Towards Foundations for Programmable Overlay Networks and Overlay Computing Systems}},
publisher = {Springer},
volume = {4912},
pages = {90-107},
series = {Lecture Notes in Computer Science},
booktitle = {3rd Symposium on Trustworthy Global Computing (TGC 2007)},
year = {2007},
month = nov,
address = {Sophia Antipolis, France},
PDF = {http://www-sop.inria.fr/mascotte/Luigi.Liquori/PAPERS/tgc-07.pdf},
sorte = "conf-int"
}
-
L. Liquori and M. Cosnard.
Weaving Arigatoni with a Graph Topology.
In International Conference on Advanced Engineering Computing and Applications in Sciences (ADVCOMP 2007),
Papeete, French Polynesia,
pages 8p,
November 2007.
IEEE Computer Society Press.
[PDF
]
@inproceedings{LiCo07a,
author = {L. Liquori and M. Cosnard},
title = {Weaving Arigatoni with a Graph Topology},
booktitle = {International Conference on Advanced Engineering Computing and Applications in Sciences (ADVCOMP 2007)},
publisher = {IEEE Computer Society Press},
address = {Papeete, French Polynesia},
year = {2007},
pages = {8p},
month = nov,
PDF = {http://www-sop.inria.fr/mascotte/Luigi.Liquori/PAPERS/advcomp-07.pdf},
sorte = "conf-int"
}
-
F. Mazoit and N. Nisse.
Monotonicity of Non-deterministic Graph Searching.
In Proceedings of the 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG),
volume 4769 of Lecture Notes in Computer Science,
Dornburg, Germany,
pages 33-44,
June 2007.
Springer.
[WWW
] [PDF
]
| Abstract: |
|
In graph searching, a team of searchers is aiming at capturing a fugitive moving in a graph. In the initial variant, called \emph{invisible graph searching}, the searchers do not know the position of the fugitive until they catch it. In another variant, the searchers permanently know the position of the fugitive, i.e. the fugitive is visible. This latter variant is called \emph{visible graph searching}. A search strategy that catches any fugitive in such a way that, the part of the graph reachable by the fugitive never grows is called \emph{monotone}. {\it A priori}, monotone strategies may require more searchers than general strategies to catch any fugitive. This is however not the case for visible and invisible graph searching. Two important consequences of the monotonicity of visible and invisible graph searching are: (1) the decision problem corresponding to the computation of the smallest number of searchers required to clear a graph is in NP, and (2) computing optimal search strategies is simplified by taking into account that there exist some that never backtrack. Fomin \emph{et al.} (2005) introduced an important graph searching variant, called \emph{non-determi\-nistic graph searching}, that unifies visible and invisible graph searching. In this variant, the fugitive is invisible, and the searchers can query an oracle that permanently knows the current position of the fugitive. The question of the monotonicity of non-deterministic graph searching is however left open. In this paper, we prove that non-deterministic graph searching is monotone. In particular, this result is a unified proof of monotonicity for visible and invisible graph searching. As a consequence, the decision problem corresponding to non-determinisitic graph searching belongs to NP. Moreover, the exact algorithms designed by Fomin \emph{et al.} do compute optimal non-deterministic search strategies. |
@inproceedings{MaNi07,
sorte = "conf-int",
author = {F. Mazoit and N. Nisse},
title = {Monotonicity of Non-deterministic Graph Searching},
booktitle = {Proceedings of the 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG)},
year = {2007},
month = jun,
pages = {33-44},
volume = {4769},
series = {Lecture Notes in Computer Science},
publisher = {Springer},
address = {Dornburg, Germany},
abstract = {In graph searching, a team of searchers is aiming at capturing a fugitive moving in a graph. In the initial variant, called \emph{invisible graph searching}, the searchers do not know the position of the fugitive until they catch it. In another variant, the searchers permanently know the position of the fugitive, i.e. the fugitive is visible. This latter variant is called \emph{visible graph searching}. A search strategy that catches any fugitive in such a way that, the part of the graph reachable by the fugitive never grows is called \emph{monotone}. {\it A priori}, monotone strategies may require more searchers than general strategies to catch any fugitive. This is however not the case for visible and invisible graph searching. Two important consequences of the monotonicity of visible and invisible graph searching are: (1) the decision problem corresponding to the computation of the smallest number of searchers required to clear a graph is in NP, and (2) computing optimal search strategies is simplified by taking into account that there exist some that never backtrack. Fomin \emph{et al.} (2005) introduced an important graph searching variant, called \emph{non-determi\-nistic graph searching}, that unifies visible and invisible graph searching. In this variant, the fugitive is invisible, and the searchers can query an oracle that permanently knows the current position of the fugitive. The question of the monotonicity of non-deterministic graph searching is however left open. In this paper, we prove that non-deterministic graph searching is monotone. In particular, this result is a unified proof of monotonicity for visible and invisible graph searching. As a consequence, the decision problem corresponding to non-determinisitic graph searching belongs to NP. Moreover, the exact algorithms designed by Fomin \emph{et al.} do compute optimal non-deterministic search strategies.},
url = {http://www.informatik.uni-trier.de/~ley/db/conf/wg/wg2007.shtml},
pdf = {http://www-sop.inria.fr/members/Nicolas.Nisse/publications/WG07.ps}
}
-
N. Nepomuceno,
P. R. Pinheiro,
and A. L. V. Coelho.
Combining Metaheuristics and Integer Linear Programming: A Hybrid Methodology Applied to the Container Loading Problem.
In XX Concurso de Teses e Dissertações (CTD),
Rio de Janeiro, Brazil,
pages 2028-2032,
2007.
[PDF
]
@inproceedings{NPC07b,
author = {N. Nepomuceno and P. R. Pinheiro and A. L. V. Coelho},
OPTauthor = {Napole{\~a}o Nepomuceno and Pl{\'a}cido Rog{\'e}rio Pinheiro and Andr{\'e} L. V. Coelho},
title = {Combining Metaheuristics and Integer Linear Programming: A Hybrid Methodology Applied to the Container Loading Problem},
booktitle = {XX Concurso de Teses e Disserta\c{c}\~oes (CTD)},
address= {Rio de Janeiro, Brazil},
year = {2007},
pages = {2028-2032},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/NPC07b.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={no},
x-pays = {BR},
sorte = "conf-nat",
}
-
N. Nepomuceno,
P. R. Pinheiro,
and A. L. V. Coelho.
Tackling the Container Loading Problem: A Hybrid Approach Based on Integer Linear Programming and Genetic Algorithms.
In 7th European Conference on Evolutionary Computation in Combinatorial Optimization (EvoCOP),
Valencia, Spain,
pages 154-165,
2007.
[WWW
] [PDF
]
@inproceedings{NPC07a,
author = {N. Nepomuceno and P. R. Pinheiro and A. L. V. Coelho},
OPTauthor = {Napole{\~a}o Nepomuceno and Pl{\'a}cido Rog{\'e}rio Pinheiro and Andr{\'e} L. V. Coelho},
title = {Tackling the Container Loading Problem: A Hybrid Approach Based on Integer Linear Programming and Genetic Algorithms},
booktitle = {7th European Conference on Evolutionary Computation in Combinatorial Optimization (EvoCOP)},
address= {Valencia, Spain},
year = {2007},
pages = {154-165},
url = {http://dx.doi.org/10.1007/978-3-540-71615-0_14},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/NPC07.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {BR},
sorte = "conf-int",
}
-
N. Nisse and D. Soguet.
Graph Searching with Advice.
In Proceedings of the 14th International Colloquium on Structural Information and Communication Complexity (SIROCCO),
volume 4474 of Lecture Notes in Computer Science,
Castiglioncello, Italy,
pages 51-65,
June 2007.
Springer.
[WWW
] [PDF
]
| Abstract: |
|
Fraigniaud {\it et al.} (2006) introduced a new measure of difficulty for a distributed task in a network. The smallest {\it number of bits of advice} of a distributed problem is the smallest number of bits of information that has to be available to nodes in order to accomplish the task efficiently. Our paper deals with the number of bits of advice required to perform efficiently the graph searching problem in a distributed setting. In this variant of the problem, all searchers are initially placed at a particular node of the network. The aim of the team of searchers is to capture an invisible and arbitrarily fast fugitive in a monotone connected way, i.e., the cleared part of the graph is permanently connected, and never decreases while the search strategy is executed. We show that the minimum number of bits of advice permitting the monotone connected clearing of a network in a distributed setting is $O (n \log n)$, where $n$ is the number of nodes of the network, and this bound is tight. More precisely, we first provide a labelling of the vertices of any graph $G$, using a total of $O(n \log n)$ bits, and a protocol using this labelling that enables clearing $G$ in a monotone connected distributed way. Then, we show that this number of bits of advice is almost optimal: no protocol using an oracle providing $o(n \log n)$ bits of advice permits the monotone connected clearing of a network using the smallest number of searchers. |
@inproceedings{NiSo07,
sorte = "conf-int",
author = {N. Nisse and D. Soguet},
title = {Graph Searching with Advice},
booktitle = {Proceedings of the 14th International Colloquium on Structural Information and Communication Complexity (SIROCCO)},
year = {2007},
month = jun,
pages = {51-65},
volume = {4474},
series = {Lecture Notes in Computer Science},
publisher = {Springer},
address = {Castiglioncello, Italy},
abstract = {Fraigniaud {\it et al.} (2006) introduced a new measure of difficulty for a distributed task in a network. The smallest {\it number of bits of advice} of a distributed problem is the smallest number of bits of information that has to be available to nodes in order to accomplish the task efficiently. Our paper deals with the number of bits of advice required to perform efficiently the graph searching problem in a distributed setting. In this variant of the problem, all searchers are initially placed at a particular node of the network. The aim of the team of searchers is to capture an invisible and arbitrarily fast fugitive in a monotone connected way, i.e., the cleared part of the graph is permanently connected, and never decreases while the search strategy is executed. We show that the minimum number of bits of advice permitting the monotone connected clearing of a network in a distributed setting is $O (n \log n)$, where $n$ is the number of nodes of the network, and this bound is tight. More precisely, we first provide a labelling of the vertices of any graph $G$, using a total of $O(n \log n)$ bits, and a protocol using this labelling that enables clearing $G$ in a monotone connected distributed way. Then, we show that this number of bits of advice is almost optimal: no protocol using an oracle providing $o(n \log n)$ bits of advice permits the monotone connected clearing of a network using the smallest number of searchers.},
url = {http://www.informatik.uni-trier.de/~ley/db/conf/sirocco/sirocco2007.shtml},
pdf = {http://www-sop.inria.fr/members/Nicolas.Nisse/publications/Sirocco07.ps}
}
-
N. Nisse and D. Soguet.
Stratégies d'encerclement avec information.
In 9èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel),
pages 49-52,
2007.
[WWW
] [PDF
]
| Abstract: |
|
Dans le cadre de l'algorithmique r\'eparti dans les r\'eseaux, l'efficacit\'e d'un algorithme d\'epend tr\`es fortement de la connaissance du r\'eseau, disponible {\it a priori}. Tr\`es souvent, cette connaissance {\it a priori} est de nature qualitative (taille du r\'eseau, son diam\`etre, etc.). Fraigniaud {\it et al.} (2006) ont introduit une mesure quantitative de la complexit\'e d'une tâche r\'epartie dans un r\'eseau. Etant donn\'e un probl\`eme r\'eparti, cette mesure, {\it la taille d'oracle}, consiste en le plus petit nombre de bits d'information dont doit disposer l'algorithme pour r\'esoudre le probl\`eme efficacement. Nous nous int\'eressons \`a la taille d'oracle permettant de r\'esoudre efficacement {\it l'encerclement} dans les graphes. L'encerclement dans les r\'eseaux vise \`a r\'ealiser la capture d'un fugitif invisible, arbitrairement rapide et omniscient, par une \'equipe d'agents mobiles, dans un r\'eseau. La strat\'egie d'encerclement est calcul\'ee en temps r\'eel, par les agents eux mêmes, et doit v\'erifier les trois propri\'et\'es suivantes: (1)~{\it connexit\'e} : la zone nettoy\'ee doit toujours être connexe, (2)~{\it monotonie} : la zone nettoy\'ee ne doit jamais être recontamin\'ee, et (3)~{\it optimalit\'e} : le nombre d'agents utilis\'es doit être le plus petit possible. Les deux premi\`eres contraintes assurent des communications s\'ecuris\'ees entre les agents, ainsi qu'un temps de nettoyage polynomial en la taille du r\'eseau. La troisi\`eme propri\'et\'e assure une taille minimum des ressources utilis\'ees. La seule connaissance, concernant le r\'eseau, dont les agents disposent {\it a priori}, est mod\'elis\'ee par un {\it oracle} qui r\'epartit sur les n{\oe}uds du r\'eseau une chaîne de bits d'information. Nous prouvons que la taille d'oracle pour r\'esoudre l'encerclement est $O(n \log n)$ bits, avec $n$ la taille du r\'eseau, et que cette borne est optimale. Plus pr\'ecis\'ement, nous proposons un \'etiquetage des sommets, de taille $O(n \log n)$ bits, et un protocole r\'eparti utilisant cet \'etiquetage. Ce protocole permet \`a une \'equipe d'agents, dont la m\'emoire est de taille $O(\log n)$ bits, de nettoyer le r\'eseau de façon optimale monotone et connexe. Ce protocole am\'eliore le protocole propos\'e par Blin {\it et al.} (2006) qui ne dispose d'aucune information {\it a priori} et, de ce fait, n\'ecessite un temps de nettoyage exponentiel. De plus, nous prouvons qu'il n'existe pas de protocole r\'eparti utilisant un oracle de taille $o(n \log n)$ bits qui permette de nettoyer tous les r\'eseaux de façon optimale monotone et connexe. |
@InProceedings{NiSo07,
sorte = "conf-nat",
author = {N. Nisse and D. Soguet},
title = {Strat\'egies d'encerclement avec information},
booktitle = {9\`emes Rencontres Francophones sur les Aspects Algorithmiques de T\'el\'ecommunications (AlgoTel)},
year = {2007},
pages ={49-52},
url = {http://algotel2007.labri.fr/},
pdf = {http://www-sop.inria.fr/members/Nicolas.Nisse/publications/Algotel07.pdf},
abstract = {Dans le cadre de l'algorithmique r\'eparti dans les r\'eseaux, l'efficacit\'e d'un algorithme d\'epend tr\`es fortement de la connaissance du r\'eseau, disponible {\it a priori}. Tr\`es souvent, cette connaissance {\it a priori} est de nature qualitative (taille du r\'eseau, son diam\`etre, etc.). Fraigniaud {\it et al.} (2006) ont introduit une mesure quantitative de la complexit\'e d'une tâche r\'epartie dans un r\'eseau. Etant donn\'e un probl\`eme r\'eparti, cette mesure, {\it la taille d'oracle}, consiste en le plus petit nombre de bits d'information dont doit disposer l'algorithme pour r\'esoudre le probl\`eme efficacement. Nous nous int\'eressons \`a la taille d'oracle permettant de r\'esoudre efficacement {\it l'encerclement} dans les graphes. L'encerclement dans les r\'eseaux vise \`a r\'ealiser la capture d'un fugitif invisible, arbitrairement rapide et omniscient, par une \'equipe d'agents mobiles, dans un r\'eseau. La strat\'egie d'encerclement est calcul\'ee en temps r\'eel, par les agents eux mêmes, et doit v\'erifier les trois propri\'et\'es suivantes: (1)~{\it connexit\'e} : la zone nettoy\'ee doit toujours être connexe, (2)~{\it monotonie} : la zone nettoy\'ee ne doit jamais être recontamin\'ee, et (3)~{\it optimalit\'e} : le nombre d'agents utilis\'es doit être le plus petit possible. Les deux premi\`eres contraintes assurent des communications s\'ecuris\'ees entre les agents, ainsi qu'un temps de nettoyage polynomial en la taille du r\'eseau. La troisi\`eme propri\'et\'e assure une taille minimum des ressources utilis\'ees. La seule connaissance, concernant le r\'eseau, dont les agents disposent {\it a priori}, est mod\'elis\'ee par un {\it oracle} qui r\'epartit sur les n{\oe}uds du r\'eseau une chaîne de bits d'information. Nous prouvons que la taille d'oracle pour r\'esoudre l'encerclement est $O(n \log n)$ bits, avec $n$ la taille du r\'eseau, et que cette borne est optimale. Plus pr\'ecis\'ement, nous proposons un \'etiquetage des sommets, de taille $O(n \log n)$ bits, et un protocole r\'eparti utilisant cet \'etiquetage. Ce protocole permet \`a une \'equipe d'agents, dont la m\'emoire est de taille $O(\log n)$ bits, de nettoyer le r\'eseau de façon optimale monotone et connexe. Ce protocole am\'eliore le protocole propos\'e par Blin {\it et al.} (2006) qui ne dispose d'aucune information {\it a priori} et, de ce fait, n\'ecessite un temps de nettoyage exponentiel. De plus, nous prouvons qu'il n'existe pas de protocole r\'eparti utilisant un oracle de taille $o(n \log n)$ bits qui permette de nettoyer tous les r\'eseaux de façon optimale monotone et connexe.},
}
-
I. Sau and J. Zerovnik.
Optimal Permutation Routing on Mesh Networks.
In Proc. of International Network Optimization Conference (INOC 2007),
Spa, Belgium,
pages 6p,
April 2007.
[PDF
]
| Abstract: |
|
Permutation routing is used as one of the standard tests of routing algorithms. In the permutation routing problem, each processor is the origin of at most one packet and the destination of no more than one packet. The goal is to minimize the number of time steps required to route all packets to their respective destinations. Wireless mesh networks are based on plane tessellations that divide the area into cells and give rise to triangular, square, and hexagonal grids. In this paper we study permutation routing algorithms that work on finite convex subgraphs of basic grids, under the store-and-forward $\Delta$-port model. We consider algorithms implemented independently at each node, without assuming any global knowledge about the network. I.e., distributed algorithms. We describe optimal distributed permutation routing algorithms for subgraphs of triangular and square grids that need $\ell_{max}$ (the maximum over the length of the shortest path of all packets) routing steps, and show that there is no such algorithm on the hexagonal grids. Furthermore, we show that these algorithms are oblivious and translation invariant. |
@INPROCEEDINGS{SaZe07,
AUTHOR = {I. Sau and J. Zerovnik},
TITLE = {Optimal Permutation Routing on Mesh Networks},
BOOKTITLE = {Proc. of International Network Optimization Conference (INOC 2007)},
YEAR = {2007},
pages = {6p},
address = {Spa, Belgium},
month = apr,
PDF={ftp://ftp-sop.inria.fr/mascotte/Publications/SZ07.pdf},
abstract = {Permutation routing is used as one of the standard tests of routing algorithms. In the permutation routing problem, each processor is the origin of at most one packet and the destination of no more than one packet. The goal is to minimize the number of time steps required to route all packets to their respective destinations. Wireless mesh networks are based on plane tessellations that divide the area into cells and give rise to triangular, square, and hexagonal grids. In this paper we study permutation routing algorithms that work on finite convex subgraphs of basic grids, under the store-and-forward $\Delta$-port model. We consider algorithms implemented independently at each node, without assuming any global knowledge about the network. I.e., distributed algorithms. We describe optimal distributed permutation routing algorithms for subgraphs of triangular and square grids that need $\ell_{max}$ (the maximum over the length of the shortest path of all packets) routing steps, and show that there is no such algorithm on the hexagonal grids. Furthermore, we show that these algorithms are oblivious and translation invariant.},
sorte = "conf-int",
}
-
O. Amini,
D. Coudert,
and N. Nisse.
Some Results on Non-deterministic Graph Searching in Trees.
Research Report INRIA-00174965,
INRIA,
September 2007.
[WWW
] [PDF
]
| Abstract: |
|
Pathwidth and treewidth of graphs have been extensively studied for their important structural and algorithmic aspects. Determining these parameters is NP-complete in general, however it becomes linear time solvable when restricted to some special classes of graphs. In particular, many algorithms have been proposed to compute efficiently the pathwidth of trees. Skodinis (2000) proposes a linear time algorithm for this task. Pathwidth and treewidth have also been studied for their nice game-theoretical interpretation, namely graph searching games. Roughly speaking, graph searching problems look for the smallest number of searchers that are sufficient to capture a fugitive in a graph. Fomin et al. (2005) define the non-deterministic graph searching that provides an unified approach for the pathwidth and the treewidth of a graph. Given q>=0, the q-limited search number, denotes by s_q(G), of a graph G is the smallest number of searchers required to capture an invisib le fugitive in G, such that the searchers are allowed to know the position of the fugitive at most q times. Roughly, s_0(G) corresponds to the pathwidth of a graph G, and s_\infty(G) corresponds to its treewidth. Fomin et al. proved that computing s_q(G) is NP-complete in general, and left open the complexity of the problem restricted to the class of trees. This paper studies this latter problem. On one hand, we give tight upper bounds on the number of queries required to search a tree when the number of searchers is fixed. We also prove that this number can be computed in linear time when two searchers are used. On the other hand, our main result consists in the design of a simple polynomial time algorithm that computes a 2-approximation of s_q(T), for any tree T and any q>=0. This algorithm becomes exact if q=0 or 1, which proves that the decision problem associated to s_1 is polynomial in the class of trees. |
@TechReport{ACN07,
author = {O. Amini and D. Coudert and N. Nisse},
title = {Some Results on Non-deterministic Graph Searching in Trees},
institution = {INRIA},
type = {Research Report},
number = {INRIA-00174965},
year = {2007},
month = sep,
sorte = "Rapport",
url = {http://hal.inria.fr/inria-00174965/},
pdf = {http://hal.inria.fr/action/open_file.php?url=http://hal.inria.fr/docs/00/17/50/12/PDF/AminiCoudertNisse-RR.pdf&docid=175012},
abstract = {Pathwidth and treewidth of graphs have been extensively studied for their important structural and algorithmic aspects. Determining these parameters is NP-complete in general, however it becomes linear time solvable when restricted to some special classes of graphs. In particular, many algorithms have been proposed to compute efficiently the pathwidth of trees. Skodinis (2000) proposes a linear time algorithm for this task. Pathwidth and treewidth have also been studied for their nice game-theoretical interpretation, namely graph searching games. Roughly speaking, graph searching problems look for the smallest number of searchers that are sufficient to capture a fugitive in a graph. Fomin et al. (2005) define the non-deterministic graph searching that provides an unified approach for the pathwidth and the treewidth of a graph. Given q>=0, the q-limited search number, denotes by s_q(G), of a graph G is the smallest number of searchers required to capture an invisib le fugitive in G, such that the searchers are allowed to know the position of the fugitive at most q times. Roughly, s_0(G) corresponds to the pathwidth of a graph G, and s_\infty(G) corresponds to its treewidth. Fomin et al. proved that computing s_q(G) is NP-complete in general, and left open the complexity of the problem restricted to the class of trees. This paper studies this latter problem. On one hand, we give tight upper bounds on the number of queries required to search a tree when the number of searchers is fixed. We also prove that this number can be computed in linear time when two searchers are used. On the other hand, our main result consists in the design of a simple polynomial time algorithm that computes a 2-approximation of s_q(T), for any tree T and any q>=0. This algorithm becomes exact if q=0 or 1, which proves that the decision problem associated to s_1 is polynomial in the class of trees.},
}
-
O. Amini,
L. Esperet,
and J. van den Heuvel.
Frugal Colouring of Graphs.
Research Report 6178,
INRIA,
May 2007.
[WWW
] [PDF
]
| Abstract: |
|
A $k$-frugal colouring of a graph~$G$ is a proper colouring of the vertices of~$G$ such that no colour appears more than~$k$ times in the neighbourhood of a vertex. This type of colouring was introduced by Hind, Molloy and Reed in 1997. In this paper, we study the frugal chromatic number of planar graphs, planar graphs with large girth, and outerplanar graphs, and relate this parameter with several well-studied colourings, such as colouring of the square, cyclic colouring, and $L(p,q)$-labelling. We also study frugal edge-colourings of multigraphs. |
@TechReport{AEH07,
author = {O. Amini and L. Esperet and J. {van den Heuvel}},
title = {Frugal Colouring of Graphs},
year = {2007},
month = may,
institution = {INRIA},
number = {6178},
type = {Research Report},
pdf = {http://hal.inria.fr/action/open_file.php?url=http://hal.inria.fr/docs/00/14/43/61/PDF/RR-6178.pdf&docid=144361},
url = {http://hal.inria.fr/inria-00144318/fr/},
abstract = {A $k$-frugal colouring of a graph~$G$ is a proper colouring of the vertices of~$G$ such that no colour appears more than~$k$ times in the neighbourhood of a vertex. This type of colouring was introduced by Hind, Molloy and Reed in 1997. In this paper, we study the frugal chromatic number of planar graphs, planar graphs with large girth, and outerplanar graphs, and relate this parameter with several well-studied colourings, such as colouring of the square, cyclic colouring, and $L(p,q)$-labelling. We also study frugal edge-colourings of multigraphs.},
sorte = "Rapports"
}
-
O. Amini,
F. Havet,
F. Huc,
and S. Thomassé.
WDM and Directed Star Arboricity.
Research Report 6179,
INRIA,
January 2007.
[WWW
] [PDF
]
| Abstract: |
|
Motivated by wavelength assignment for multicast in star networks, introduced by Brandt and Gonzalez [BrGo05], we study the directed star arboricity (dst) of digraphs in terms of their degree. Among other results we prove that every digraph $D$ with maximum indegree $k$ satisfies $dst(D)\leq 2k+1$, which is one short of the lower bound $2k$. Significant improvements of the bounds proposed in~\cite{BrGo05} are given. |
@TechReport{AHHT07,
author = {O. Amini and F. Havet and F. Huc and S. Thomass\'e},
title = {{WDM} and Directed Star Arboricity},
year = {2007},
month = jan,
institution = {INRIA},
number = {6179},
type = {Research Report},
url = {http://hal.inria.fr/inria-00132396/},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/AHHT07.pdf},
abstract = {Motivated by wavelength assignment for multicast in star networks, introduced by Brandt and Gonzalez [BrGo05], we study the directed star arboricity (dst) of digraphs in terms of their degree. Among other results we prove that every digraph $D$ with maximum indegree $k$ satisfies $dst(D)\leq 2k+1$, which is one short of the lower bound $2k$. Significant improvements of the bounds proposed in~\cite{BrGo05} are given.},
sorte = "Rapports"
}
-
O. Amini,
F. Mazoit,
N. Nisse,
and S. Thomassé.
Submodular partition functions.
Technical report RR-1427-07,
LABRI, Univ. Bordeaux,
April 2007.
Note: Submitted in SIAM J. discrete Maths. [PDF
]
| Abstract: |
|
we propose a new proof of the duality between the bramble-number of a graph and its tree-width. This proof is based on a new definition of submodularity on partition functions which naturally extends the usual one on set functions. The technique simplifies the proof of bramble/tree-width duality. The proof does not rely on Menger's theorem, and thus simplifies the proof of the bramble/tree-width duality. It provides a dual for matroid tree-width and one can also derive all known dual notions of other classical width-parameters from it. |
@TechReport{AMNT07,
author = {O. Amini and F. Mazoit and N. Nisse and S. Thomass\'e},
title = {Submodular partition functions},
institution = {LABRI, Univ. Bordeaux},
number = {RR-1427-07},
note = {Submitted in SIAM J. discrete Maths.},
year = {2007},
month = apr,
url = {},
pdf = {http://www.labri.fr/perso/lepine/Rapports_internes/RR-142707.pdf.gz},
abstract = { we propose a new proof of the duality between the bramble-number of a graph and its tree-width. This proof is based on a new definition of submodularity on partition functions which naturally extends the usual one on set functions. The technique simplifies the proof of bramble/tree-width duality. The proof does not rely on Menger's theorem, and thus simplifies the proof of the bramble/tree-width duality. It provides a dual for matroid tree-width and one can also derive all known dual notions of other classical width-parameters from it.}
}
-
O. Amini,
S. Pérennes,
and I. Sau.
Hardness and Approximation of Traffic Grooming.
Research Report 6236,
INRIA,
June 2007.
[WWW
] [PDF
]
| Abstract: |
|
Traffic grooming is a central problem in optical networks. It refers to pack low rate signals into higher speed streams, in order to improve bandwidth utilization and reduce network cost. In WDM networks, the most accepted criterion is to minimize the number of electronic terminations, namely the number of SONET Add-Drop Multiplexers (ADMs). In this article we focus on ring and path topologies. On the one hand, we provide the first inapproximability result for \textsc{Traffic Grooming} for fixed values of the grooming factor $g$, answering affirmatively the conjecture of Chow and Lin (\emph{Networks, 44:194-202, 2004}). More precisely, we prove that \textsc{Ring Traffic Grooming} for fixed $g\geq 1$ and \textsc{Path Traffic Grooming} for fixed $g\geq 2$ are \textsc{APX}-complete. That is, they do not accept a PTAS unless $\textsc{P}=\textsc{NP}$. Both results rely on the fact that finding the maximum number of edge-disjoint triangles in a graph (and more generally cycles of length $2g+1$ in a graph of girth $2g+1$) is \textsc{APX}-complete. On the other hand, we provide a polynomial-time approximation algorithm for \textsc{Ring} and \textsc{Path Traffic Grooming}, based on a greedy cover algorithm, with an approximation ratio independent of $g$. Namely, the approximation guarantee is $\mathcal{O}(n^{1/3} \log^2 n)$ for any $g \geq 1$, $n$ being the size of the network. This is useful in practical applications, since in backbone networks the grooming factor is usually greater than the network size. As far as we know, this is the first approximation algorithm with this property. Finally, we improve this approximation ratio under some extra assumptions about the request graph. |
@TechReport{APS07b,
author = {O. Amini and S. P\'erennes and I. Sau},
title = {Hardness and Approximation of Traffic Grooming},
year = {2007},
month = jun,
institution = {INRIA},
number = {6236},
type = {Research Report},
url = {http://hal.inria.fr/inria-00158341/fr/},
pdf = {http://hal.inria.fr/action/open_file.php?url=http://hal.inria.fr/docs/00/15/98/87/PDF/RR-groupage.pdf&docid=159887},
abstract = {Traffic grooming is a central problem in optical networks. It refers to pack low rate signals into higher speed streams, in order to improve bandwidth utilization and reduce network cost. In WDM networks, the most accepted criterion is to minimize the number of electronic terminations, namely the number of SONET Add-Drop Multiplexers (ADMs). In this article we focus on ring and path topologies. On the one hand, we provide the first inapproximability result for \textsc{Traffic Grooming} for fixed values of the grooming factor $g$, answering affirmatively the conjecture of Chow and Lin (\emph{Networks, 44:194-202, 2004}). More precisely, we prove that \textsc{Ring Traffic Grooming} for fixed $g\geq 1$ and \textsc{Path Traffic Grooming} for fixed $g\geq 2$ are \textsc{APX}-complete. That is, they do not accept a PTAS unless $\textsc{P}=\textsc{NP}$. Both results rely on the fact that finding the maximum number of edge-disjoint triangles in a graph (and more generally cycles of length $2g+1$ in a graph of girth $2g+1$) is \textsc{APX}-complete. On the other hand, we provide a polynomial-time approximation algorithm for \textsc{Ring} and \textsc{Path Traffic Grooming}, based on a greedy cover algorithm, with an approximation ratio independent of $g$. Namely, the approximation guarantee is $\mathcal{O}(n^{1/3} \log^2 n)$ for any $g \geq 1$, $n$ being the size of the network. This is useful in practical applications, since in backbone networks the grooming factor is usually greater than the network size. As far as we know, this is the first approximation algorithm with this property. Finally, we improve this approximation ratio under some extra assumptions about the request graph.},
sorte = "Rapports"
}
-
O. Amini,
I. Sau,
and S. Saurabh.
Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem.
Research Report 6237,
INRIA,
June 2007.
[WWW
] [PDF
]
| Abstract: |
|
In this paper we initiate the study of finding an induced subgraph of size at most $k$ with minimum degree at least $d$. We call this problem \sc Minimum Subgraph of Minimum Degree $_{\geq d}$ (MSMD$_d$). For $d=2$, it corresponds to finding a shortest cycle of the graph. The problem is strongly related to the \textsc{Dense $k$-Subgraph} problem and is of interest in practical applications. We show that the {\sc MSMS}$_d$ is fixed parameter intractable for $d\geq 3$ in general graphs by showing it to be W[1]-hard by a reduction from {\sc Multi-Color Clique}. On the algorithmic side, we show that the problem is fixed parameter tractable in graphs which excluded minors and graphs with bounded local tree-width. In particular, this implies that the problem is fixed parameter tractable in planar graphs, graphs of bounded genus and graphs with bounded maximum degree. |
@TechReport{ASS07,
author = {O. Amini and I. Sau and S. Saurabh},
title = {Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem},
year = {2007},
month = jun,
institution = {INRIA},
number = {6237},
type = {Research Report},
url = {http://hal.inria.fr/inria-00157970/en/},
pdf = {http://hal.inria.fr/action/open_file.php?url=http://hal.inria.fr/docs/00/15/96/85/PDF/RR-6237.pdf&docid=159685},
abstract = {In this paper we initiate the study of finding an induced subgraph of size at most $k$ with minimum degree at least $d$. We call this problem \sc Minimum Subgraph of Minimum Degree $_{\geq d}$ (MSMD$_d$). For $d=2$, it corresponds to finding a shortest cycle of the graph. The problem is strongly related to the \textsc{Dense $k$-Subgraph} problem and is of interest in practical applications. We show that the {\sc MSMS}$_d$ is fixed parameter intractable for $d\geq 3$ in general graphs by showing it to be W[1]-hard by a reduction from {\sc Multi-Color Clique}. On the algorithmic side, we show that the problem is fixed parameter tractable in graphs which excluded minors and graphs with bounded local tree-width. In particular, this implies that the problem is fixed parameter tractable in planar graphs, graphs of bounded genus and graphs with bounded maximum degree.},
sorte = "Rapports"
}
-
J-C. Bermond,
I. Caragiannis,
D. Coudert,
C. Gomes,
I. Guerin-Lassous,
G. Huiban,
C. Molle,
and I. Sau.
Algorithmic solutions for critical resource sharing: second year.
Technical report Deliverable 2.2.2,
IST FET AEOLUS, Integrated Project IST-015964,
2007.
[PDF
]
@TechReport{BCC+07,
author = {J-C. Bermond and I. Caragiannis and D. Coudert and C. Gomes and I. {Guerin-Lassous} and G. Huiban and C. Molle and I. Sau},
title = {Algorithmic solutions for critical resource sharing: second year},
institution = {IST FET AEOLUS, Integrated Project IST-015964},
year = {2007},
number = {Deliverable 2.2.2},
pdf = {http://aeolus.ceid.upatras.gr/sub-projects/deliverables/D222.pdf},
sorte = "Rapports"
}
-
J-C. Bermond,
D. Coudert,
and B. Leveque.
Approximations for All-to-all Uniform Traffic Grooming on Unidirectional Ring.
Technical report inria-00175795,
hal,
October 2007.
[WWW
] [PDF
]
| Abstract: |
|
Traffic grooming in a WDM network consists of assigning to each request (lightpath) a wavelength with the constraint that a given wavelength can carry at most C requests or equivalently a request uses at most 1/C of the bandwidth. C is known as the grooming ratio. A request (lightpath) need two SONET add-drop multiplexers (ADMs) at each end node~; using grooming different requests can share the same ADM. The so called traffic grooming problem consists of minimizing the total number of ADMs to be used (in order to reduce the overall cost of the network). Here we consider the traffic grooming problem in WDM unidirectional rings with all-to-all uniform unitary traffic. This problem has been optimally solved for specific values of the grooming ratio, namely C=2,3,4,5,6. In this paper we present various simple constructions for the grooming problem providing good approximation of the total number of ADMs. For that we use the fact that the problem corresponds to a partition of the edges of the complete graph into subgraphs, where each subgraph has at most C edges and where the total number of vertices has to be minimized. |
@TechReport{BCL07,
author = {J-C. Bermond and D. Coudert and B. Leveque},
title = {Approximations for All-to-all Uniform Traffic Grooming on Unidirectional Ring},
institution = {hal},
year = {2007},
OPTkey = {},
OPTtype = {},
number = {inria-00175795},
OPTaddress = {},
month = oct,
OPTnote = {},
OPTannote = {},
url = {http://hal.inria.fr/inria-00175795/en/},
abstract = {Traffic grooming in a WDM network consists of assigning to each request (lightpath) a wavelength with the constraint that a given wavelength can carry at most C requests or equivalently a request uses at most 1/C of the bandwidth. C is known as the grooming ratio. A request (lightpath) need two SONET add-drop multiplexers (ADMs) at each end node~; using grooming different requests can share the same ADM. The so called traffic grooming problem consists of minimizing the total number of ADMs to be used (in order to reduce the overall cost of the network). Here we consider the traffic grooming problem in WDM unidirectional rings with all-to-all uniform unitary traffic. This problem has been optimally solved for specific values of the grooming ratio, namely C=2,3,4,5,6. In this paper we present various simple constructions for the grooming problem providing good approximation of the total number of ADMs. For that we use the fact that the problem corresponds to a partition of the edges of the complete graph into subgraphs, where each subgraph has at most C edges and where the total number of vertices has to be minimized.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/BCL07-inria-00175795.pdf},
sorte = "Rapports"
}
-
J-C. Bermond,
V. Papadopoulou,
and E. Pitoura.
Subproject2: Resource Management Report on the activities of the second year.
Technical report Deliverable 2.O.2,
IST FET AEOLUS, Integrated Project IST-015964,
2007.
[PDF
]
@TechReport{BPP07,
author = {J-C. Bermond and V. Papadopoulou and E. Pitoura},
title = {Subproject2: Resource Management Report on the activities of the second year},
institution = {IST FET AEOLUS, Integrated Project IST-015964},
year = {2007},
number = {Deliverable 2.O.2},
pdf = {http://aeolus.ceid.upatras.gr/sub-projects/deliverables/D202.pdf},
sorte = "Rapports"
}
-
D. Coudert,
F. Huc,
F. Peix,
and M-E. Voge.
On Minimizing the Average Reliability of Connections in Multilayer Networks under Shared Risk Groups and Costs Constraints.
Technical report inria-00175813,
hal,
October 2007.
[WWW
] [PDF
]
| Abstract: |
|
The notion of Shared Risk Resource Groups (SRRG) has been introduced to capture survivability issues when a set of resources may fail simultaneously. Applied to Wavelength Division Multiplexing Network (WDM), it expresses that some links and nodes may fail simultaneously. The reliability of a connection therefore depends on the number of SRRGs through which it is routed. Consequently, this number has to be minimized. This problem has been proved NP-complete and hard to approximate in general, even when routing a single request. Some heuristics using shortest paths have already been designed, however the cost (the usual routing cost, not in term of SRRG) was not part of the objective. In this paper we study the problem of minimizing a linear combination of the average number of SRRG per paths and the cost of the routing. The main result of our work is a column generation formulation that allows to solve the problem of maximizing the reliability of a set of connection requests in MPLS/WDM mesh networks with SRRGs while keeping the cost of the routing low. |
@TechReport{CHPV07,
author = {D. Coudert and F. Huc and F. Peix and M-E. Voge},
title = {On Minimizing the Average Reliability of Connections in Multilayer Networks under Shared Risk Groups and Costs Constraints},
institution = {hal},
year = {2007},
OPTkey = {},
OPTtype = {},
number = {inria-00175813},
OPTaddress = {},
month = oct,
OPTnote = {},
OPTannote = {},
url = {http://hal.inria.fr/inria-00175813/en/},
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/CHPV07-inria-00175813.pdf},
abstract = {The notion of Shared Risk Resource Groups (SRRG) has been introduced to capture survivability issues when a set of resources may fail simultaneously. Applied to Wavelength Division Multiplexing Network (WDM), it expresses that some links and nodes may fail simultaneously. The reliability of a connection therefore depends on the number of SRRGs through which it is routed. Consequently, this number has to be minimized. This problem has been proved NP-complete and hard to approximate in general, even when routing a single request. Some heuristics using shortest paths have already been designed, however the cost (the usual routing cost, not in term of SRRG) was not part of the objective. In this paper we study the problem of minimizing a linear combination of the average number of SRRG per paths and the cost of the routing. The main result of our work is a column generation formulation that allows to solve the problem of maximizing the reliability of a set of connection requests in MPLS/WDM mesh networks with SRRGs while keeping the cost of the routing low.},
sorte = "Rapports"
}
-
D. Coudert,
S. Perennes,
H. Rivano,
and M-E. Voge.
Shared Risk Resource Groups and Colored Graph: Polynomial Cases and Transformation Issues.
Technical report inria-00175143,
HAL,
September 2007.
[WWW
] [PDF
]
| Abstract: |
|
In this paper, we characterize polynomial cases for several combinatorial optimization problems in the context of multilayer networks with shared risk resource groups. |
@TechReport{CPRV07,
author = {D. Coudert and S. Perennes and H. Rivano and M-E. Voge},
title = {Shared Risk Resource Groups and Colored Graph: Polynomial Cases and Transformation Issues},
institution = {HAL},
year = {2007},
OPTkey = {},
OPTtype = {},
number = {inria-00175143},
OPTaddress = {},
month = sep,
OPTnote = {},
OPTannote = {},
abstract = {In this paper, we characterize polynomial cases for several combinatorial optimization problems in the context of multilayer networks with shared risk resource groups. },
url = {http://hal.inria.fr/inria-00175143/fr/},
pdf = {http://hal.inria.fr/action/open_file.php?url=http://hal.inria.fr/docs/00/17/51/43/PDF/sir07.pdf&docid=175143},
sorte = "Rapports"
}
-
D. Coudert and J-S. Sereni.
Characterization of graphs and digraphs with small process number.
Research Report 6285,
INRIA,
September 2007.
[WWW
] [PDF
]
| Abstract: |
|
The process number of a digraph has been introduced as a tool to study rerouting issues in WDM networks. We consider the recognition and the characterization of (di)graphs with process number at most two. |
@TechReport{CoSe07,
author = {D. Coudert and J-S. Sereni},
title = {Characterization of graphs and digraphs with small process number},
institution = {INRIA},
year = {2007},
OPTkey = {},
type = {Research Report},
number = {6285},
OPTaddress = {},
month = sep,
OPTnote = {http\string://hal.inria.fr/inria-00171083/fr/},
OPTannote = {},
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/RR-6285.pdf},
url = {http://hal.inria.fr/inria-00171083/fr/},
abstract = {The process number of a digraph has been introduced as a tool to study rerouting issues in WDM networks. We consider the recognition and the characterization of (di)graphs with process number at most two.},
sorte = "Rapports"
}
-
J. Galtier.
Tournament MAC with constant size congestion window for WLAN.
Technical report RR-6396,
INRIA,
December 2007.
[WWW
] [PDF
]
| Abstract: |
|
In the context of radio distributed networks, we present a generalized approach for the Medium Access Control (MAC) with fixed congestion window. Our protocol is quite simple to analyze and can be used in a lot of different situations. We give mathematical evidence showing that our performance is tight, in the sense that no protocol with fixed congestion window can do better. We also place ourselves in the WiFi/WiMAX framework, and show experimental results enlightening collision reduction of 14{\%} to 21{\%} compared to the best known other methods. We show channel capacity improvement, and fairness considerations. |
@TechReport{Gal07b,
author = {J. Galtier},
title = {Tournament {MAC} with constant size congestion window for {WLAN}},
institution = {INRIA},
year = 2007,
number = {RR-6396},
month = dec,
abstract = {In the context of radio distributed networks, we present a generalized approach for the Medium Access Control (MAC) with fixed congestion window. Our protocol is quite simple to analyze and can be used in a lot of different situations. We give mathematical evidence showing that our performance is tight, in the sense that no protocol with fixed congestion window can do better. We also place ourselves in the WiFi/WiMAX framework, and show experimental results enlightening collision reduction of 14{\%} to 21{\%} compared to the best known other methods. We show channel capacity improvement, and fairness considerations.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/Gal07b.pdf},
url = {http://hal.inria.fr/inria-00195965},
sorte = "Rapports"
}
-
F. Giroire,
J. Chendrashekar,
G. Iannaccone,
T. Karagiannis,
K. Papagiannaki,
E. Schooler,
and N. Taft.
Inside the Forbidden City: A look at End-Host Traffic inside a Modern Enterprise.
Technical Report,
Intel Research,
2007.
[PDF
]
@techreport{GCI+07,
author = {F. Giroire and J. Chendrashekar and G. Iannaccone and T. Karagiannis and K. Papagiannaki and E. Schooler and N. Taft},
title = {Inside the Forbidden City: A look at End-Host Traffic inside a Modern Enterprise},
institution = {Intel Research},
type = {Technical Report},
year = {2007},
(nil)df = {http://www-sop.inria.fr/members/Frederic.Giroire/publis/GCI+07.pdf},
abstract = {},
}
-
F. Giroire,
J. Chendrashekar,
N. Taft,
G. Iannaccone,
T. Karagiannis,
K. Papagiannaki,
and E. Schooler.
The Case For Personalizing End-Host Detectors..
Technical Report,
Intel Research,
2007.
[PDF
]
@techreport{GCT+07,
author = {F. Giroire and J. Chendrashekar and N. Taft and G. Iannaccone and T. Karagiannis and K. Papagiannaki and E. Schooler},
title = {The Case For Personalizing End-Host Detectors.},
institution = {Intel Research},
type = {Technical Report},
year = {2007},
(nil)df = {http://www-sop.inria.fr/members/Frederic.Giroire/publis/GCT+07.pdf},
abstract = {},
}
-
C. Gomes and H. Rivano.
Fair Joint Routing and Scheduling Problem in Wireless Mesh Networks.
Research Report 6198,
INRIA,
May 2007.
[WWW
] [PDF
]
| Abstract: |
|
There is an increasing interest in using Wireless Mesh Networks (WMNs) as broadband backbone for next-generation wireless networking. WMNs is a scalable and cost-effective solution. Industrial standards groups are revisiting the existing protocols and they work enhanced specifications for WMNs. Wireless Mesh Networks (WMNs) are cost-effective and provide an appealing answer to connectivity issues of ubiquituous computing. One of the key challenges of WMNs is to provide guaranteed quality of service that network operator could claim. In this paper, we address the Fair Round Weighting Problem (F_RWP) and present mixed integer linear programming models for computing an optimal routing and link scheduling. We have considered two kind of transmissions scenarios, burst transmission and permanent regime, and their specific settings. |
@TECHREPORT{GoRi07,
author = {C. Gomes and H. Rivano},
title = {Fair Joint Routing and Scheduling Problem in Wireless Mesh Networks},
institution = {INRIA},
year = {2007},
type = {Research Report},
number = {6198},
month = may,
abstract = {There is an increasing interest in using Wireless Mesh Networks (WMNs) as broadband backbone for next-generation wireless networking. WMNs is a scalable and cost-effective solution. Industrial standards groups are revisiting the existing protocols and they work enhanced specifications for WMNs. Wireless Mesh Networks (WMNs) are cost-effective and provide an appealing answer to connectivity issues of ubiquituous computing. One of the key challenges of WMNs is to provide guaranteed quality of service that network operator could claim. In this paper, we address the Fair Round Weighting Problem (F_RWP) and present mixed integer linear programming models for computing an optimal routing and link scheduling. We have considered two kind of transmissions scenarios, burst transmission and permanent regime, and their specific settings.},
url = {https://hal.inria.fr/inria-00148957},
pdf = {http://hal.inria.fr/action/open_file.php?url=http://hal.inria.fr/docs/00/14/90/25/PDF/RR-6198.pdf&docid=149025},
sorte = "Rapports"
}
-
F. Havet,
R. Kang,
and J.-S. Sereni.
Improper colouring of unit disk graphs.
Research Report 6206,
INRIA,
May 2007.
[WWW
] [PDF
]
| Abstract: |
|
Motivated by a satellite communications problem, we consider a generalised colouring problem on unit disk graphs. A colouring is k -improper if no vertex receives the same colour as k +1 of its neighbours. The k -improper chromatic number chi_k (G) is the least number of colours needed in a k -improper colouring of a graph G. The main sub ject of this work is analysing the complexity of computing chi_k for the class of unit disk graph and some related classes, e.g. hexagonal graphs and interval graphs. We show NP-completeness in many restricted cases and also provide both positive and negative approximability results. Due to the challenging nature of this topic, many seemingly simple questions remain: for example, it remains open to determine the complexity of computing k for unit interval graphs. |
@TechReport{HKS07,
author = {F. Havet and R. Kang and J.-S. Sereni},
title = {Improper colouring of unit disk graphs},
year = {2007},
month = may,
institution = {INRIA},
number = {6206},
type = {Research Report},
pages = {38 p.},
url= {https://hal.inria.fr/inria-00150464},
pdf = {https://hal.inria.fr/action/open_file.php?url=https://hal.inria.fr/docs/00/15/06/27/PDF/RR-6206.pdf&docid=150627},
abstract = {Motivated by a satellite communications problem, we consider a generalised colouring problem on unit disk graphs. A colouring is k -improper if no vertex receives the same colour as k +1 of its neighbours. The k -improper chromatic number chi_k (G) is the least number of colours needed in a k -improper colouring of a graph G. The main sub ject of this work is analysing the complexity of computing chi_k for the class of unit disk graph and some related classes, e.g. hexagonal graphs and interval graphs. We show NP-completeness in many restricted cases and also provide both positive and negative approximability results. Due to the challenging nature of this topic, many seemingly simple questions remain: for example, it remains open to determine the complexity of computing k for unit interval graphs.},
sorte = "Rapports",
}
-
F. Havet and S. Thomasse.
Complexity of $(p,1)$-total labelling.
Research Report 6305,
INRIA,
September 2007.
[WWW
] [PDF
]
| Abstract: |
|
A \it $(p,1)$-total labelling of a graph $G=(V,E)$ is a total coloring $L$ from $V\cup E$ into $0,\dots ,l$ such that $|L(v)-L(e)|\geq 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 $\lambda_p(G)$. The case $p=1$ corresponds to the usual notion of total colouring, which is NP-hard to calculate even for cubic bipartite graphs [MDSA94]. We assume $p\geq 2$ in this paper. It is easy to show that $\lambda_p(G)\geq \Delta +p-1$, where $\Delta$ is the maximum degree of $G$. Moreover, when $G$ is bipartite, $\Delta +p$ is an upper bound for $\lambda_p(G)$, leaving only two possible values. In this paper, we completely settle the computational complexity of deciding whether $\lambda_p(G)$ is equal to $\Delta +p-1$ or to $\Delta +p$ when $G$ is bipartite. This is trivial when $\Delta \leq p$, polynomial when $\Delta =3$ and $p=2$, and NP-complete in the remaining cases. |
@TechReport{HaTh07,
author = {F. Havet and S. Thomasse},
title = {Complexity of $(p,1)$-total labelling},
year = {2007},
month = sep,
institution = {INRIA},
number = {6305},
type = {Research Report},
url= {https://hal.inria.fr/inria-00173438},
pdf = {https://hal.inria.fr/action/open_file.php?url=https://hal.inria.fr/docs/00/17/52/95/PDF/RR-6305.pdf&docid=175295},
abstract = {A \it $(p,1)$-total labelling of a graph $G=(V,E)$ is a total coloring $L$ from $V\cup E$ into $0,\dots ,l$ such that $|L(v)-L(e)|\geq 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 $\lambda_p(G)$. The case $p=1$ corresponds to the usual notion of total colouring, which is NP-hard to calculate even for cubic bipartite graphs [MDSA94]. We assume $p\geq 2$ in this paper. It is easy to show that $\lambda_p(G)\geq \Delta +p-1$, where $\Delta$ is the maximum degree of $G$. Moreover, when $G$ is bipartite, $\Delta +p$ is an upper bound for $\lambda_p(G)$, leaving only two possible values. In this paper, we completely settle the computational complexity of deciding whether $\lambda_p(G)$ is equal to $\Delta +p-1$ or to $\Delta +p$ when $G$ is bipartite. This is trivial when $\Delta \leq p$, polynomial when $\Delta =3$ and $p=2$, and NP-complete in the remaining cases.},
sorte = "Rapports",
}
-
R. Klasing,
Z. Lotker,
A. Navarra,
and S. Pérennes.
From Balls and Bins to Points and Vertices.
Technical Report RR-1437-07,
LaBRI,
October 2007.
@TechReport{KLNP07,
author = "R. Klasing and Z. Lotker and A. Navarra and S. P\'erennes",
title = "From Balls and Bins to Points and Vertices",
institution = "LaBRI",
number = "RR-1437-07",
month = oct,
year = "2007",
type = "Technical Report",
sorte = "Rapports",
}
-
L. Liquori,
D. Borsetti,
C. Casetti,
and C. Chiasserini.
Overlay Networks for Vehicular Networks.
Research Report,
Politecnico di Torino,
2007.
@TechReport{LBCC07,
author = {L. Liquori and D. Borsetti and C. Casetti and C. Chiasserini},
title = {{Overlay Networks for Vehicular Networks}},
institution = {Politecnico di Torino},
OPTnumber = {to be given},
type = {Research Report},
year = {2007},
sorte = "Rapports"
}
-
C. Molle,
F. Peix,
and H. Rivano.
Cross-Layer Design for Wireless Mesh Networks Using Column Generation.
Technical report 6448,
INRIA,
December 2007.
[WWW
] [PDF
]
| Abstract: |
|
Wireless Mesh Networks (WMNs) have become an interesting answer for broadband wireless networking. Cross-layer optimization problems for WMNs deployment and management are necessary and challenging. In this paper we focus on jointly optimizing routing and link scheduling in a single-channel wireless mesh network, in order to maximize fair network throughput or equivalently minimize time period. Our approach is based on a path/configuration linear formulation of the joint routing and scheduling problem, which is solved by column generation with two auxiliary programs to generate new paths and configurations. The method is validated on small topologies from an optimal node/arc formulation, and simulations are then done on random and grid topologies. |
@TechReport{MPR07,
author = {C. Molle and F. Peix and H. Rivano},
title = {Cross-Layer Design for Wireless Mesh Networks Using Column Generation},
institution = {INRIA},
year = {2007},
number = {6448},
month = dec,
url = {http://hal.inria.fr/inria-00193420/en/},
pdf = {http://hal.inria.fr/action/open_file.php?url=http://hal.inria.fr/docs/00/19/34/20/PDF/Rapport.pdf&docid=193420},
abstract = {Wireless Mesh Networks (WMNs) have become an interesting answer for broadband wireless networking. Cross-layer optimization problems for WMNs deployment and management are necessary and challenging. In this paper we focus on jointly optimizing routing and link scheduling in a single-channel wireless mesh network, in order to maximize fair network throughput or equivalently minimize time period. Our approach is based on a path/configuration linear formulation of the joint routing and scheduling problem, which is solved by column generation with two auxiliary programs to generate new paths and configurations. The method is validated on small topologies from an optimal node/arc formulation, and simulations are then done on random and grid topologies.},
sorte = "Rapports",
}
-
P. Nain,
C. Casetti,
and L. Liquori.
A Stochastic Model of an Arigatoni Overlay Computer.
Research Report to be given,
Politecnico di Torino,
2007.
@TechReport{CLN07,
author = {P. Nain and C. Casetti and L. Liquori},
title = {{A Stochastic Model of an Arigatoni Overlay Computer }},
institution = {Politecnico di Torino},
number = {to be given},
type = {Research Report},
year = {2007},
sorte = "Rapports"
}
-
S. Teigen.
Distributing OSA Simulations using FractalRMI.
Technical Report,
INRIA,
2007.
Note: Unpublished, internal document.
@TechReport{Tei07a,
author = {S. Teigen},
title = {Distributing {OSA} Simulations using {FractalRMI}},
institution = {INRIA},
year = {2007},
OPTkey = {},
type = {Technical Report},
OPTnumber = {},
OPTaddress = {},
OPTmonth = {},
note = {Unpublished, internal document.},
OPTannote = {},
sorte = "Rapports",
}
