This paper presents a new method and a constraint-based objective function to solve two problemsrelated to the design of optical telecommunication networks, namely the Synchronous Optical Net-work Ring Assignment Problem (SRAP) and the Intra-ring Synchronous Optical Network DesignProblem (IDP). These network topology problems can be represented as a graph partitioning withcapacity constraints as shown in previous works. We present here a new objective function and anew local search algorithm to solve these problems. Experiments conducted in C
The two other methods described in @cite_5 are based on the idea that to save ADMs a good solution should have very dense rings. They are both greedy and rely on a clique algorithm. In graph theory, a clique in an undirected graph @math is a subset of the vertex set @math , such that for every two vertices in @math , there exists an edge connecting the two. Finding a clique is not that easy, a way to do it is to use an "Union-Find" strategie, two clique @math and @math such that each node in @math is adjacent to each node in @math then merge the two cliques (). The associated heuristic starts by considering each node to be a clique of size one, and to merge two cliques into a larger clique until there are no more possible merges.
@cite_5
1969385974
Consider algorithms with unbounded computation time that probe the entries of the adjacency matrix of an @math vertex graph, and need to output a clique. We show that if the input graph is drawn at random from @math (and hence is likely to have a clique of size roughly @math ), then for every @math and constant @math , there is an @math (that may depend on @math and @math ) such that no algorithm that makes @math probes in @math rounds is likely (over the choice of the random graph) to output a clique of size larger than @math .