Search

We propose a multivariable continuous polynomial optimization formulation to find arbitrary maximal independent sets of any size for any graph. A local optima of the optimization problem yields a maximal independent set, while the global optima yields a maximum independent set. The solution is two phases. The first phase is listing all the maximal cliques of the graph and the second phase is solving the optimization problem. We believe that our algorithm is efficient for sparse graphs, for which there exist fast algorithms to list their maximal cliques. Our algorithm was tested on some of the DIMACS maximum clique benchmarks and produced results efficiently. In some cases our algorithm outperforms other algorithms, such as cliquer.

In this work we compare two models to calculate the capacity of multihop wireless networks. The first model utilizes the maximal independent sets of the conflict graph. The problem in that model is formulated as a linear program. The second model in our comparison utilizes the maximal cliques of the conflict graph using integer programming. We see the second model is much more efficient in calculating the capacity for larger networks. We make no assumption on the interference models and we only model it by assuming a conflict matrix. First, we prove there is a periodic schedule for the flow, by using that we formulate our integer programming model to attain maximum capacity for the network. We consider one source of data and one destination i.e. a single commodity network.

Path selection in multihop wireless networks is a hard problem. Given a performance goal, the best approach remains unclear. In hardwired networks, network flow may be maximized by using shortest path over link weights that are determined by a linear program to a multicommodity flow formulation. In this poster we generalize this linear program to include interference and mobility. We show that "In a static wireless multihop network If we route packets using any other algorithm than shortest path with links weights determined by the solution of the dual problem of maximizing the minimum spare capacity after adding the interference constraints, then the network flow saturates before reaching the maximum when we increase the demands, while we can always increase demands until we reach the maximum flow supported by the network, if we use shortest path with links weights determined as stated above. The same is true for mobile wireless multi-hop networks under protocol interference model if nodes are available within each other transmission, interference ranges within constant probabilities".

Finding the maximum flow, or capacity, of wireless multihop networks received a considerable attention by the research community due to its importance from theoretical and practical standpoints. However, since it is np-hard, only bounds can be found using different heuristics. In this poster we find an upper bound on the maximum flow supported by static wireless multihop networks for any load matrix and arbitrary topology in a polynomial time, via a Linear Program, by exploiting only a local interference conflict graph. By noting that interference is local, we replace the optimization problem condition of listing maximal independent sets by listing maximal cliques which improves computational complexity of the solution. Doing this, we had a quadratic programming problem to calculate the exact maximum flow, and not bounds, for any network which is polynomial for some interference models such as the Unit Disk Graph. We applied our model to an example network in [1] and obtained the exact maximum network flow, while [1] suggests only a solution to calculate bounds for the network. The model was also applied to other networks such that the conflict-graph is not perfect, where other models fail to calculate the capacity, and we were able of obtaining the exact capacity.