Instantly Decodable Network Coding for Completion Time or Decoding Delay Reduction in Cooperative Data Exchange Systems
19
Citation
40
Reference
10
Related Paper
Citation Trend
Abstract:
In this paper, we investigate the use of instantly decodable network coding (IDNC) for improving two fundamental performance metrics, namely, the completion time (as a measure of throughput) and mean decoding delay, in multicast cooperative data exchange (CDE) systems, where a group of geographically close clients cooperate with each other to obtain their missing packets. Here, an IDNC scheme is used for the transmissions across these clients. We utilize the stochastic shortest path (SSP) technique to study the minimum mean completion time problem. However, since finding the optimum solution is intractable, we use the obtained formulation to draw some theoretical guidelines to heuristically find solutions that can efficiently reduce the completion time. Second, we formulate the minimum mean decoding delay problem as selecting the appropriate maximal clique over well-structured graphs at the clients, and in order to reduce its complexity, we propose a simple heuristic algorithm for it. The effectiveness of our proposed algorithms is verified through extensive simulations and comparisons with existing techniques.Keywords:
Linear network coding
Clique
Clique problem
Abstract By analyzing the dynamic behaviors of the transiently chaotic neural network, we present a improved transiently chaotic neural network(TCNN) model for combinatorial optimization problems and test it on the maximum clique problem. Extensive simulations are performed and the results show that the improved transiently chaotic neural network model can yield satisfactory results on both some graphs of the DIMACS clique instances in the second DIMACS challenge and p-random graphs. It is superior to other algorithms in light of the solution quality and CPU time. Moreover, the improved model uses fewer steps to converge to saturated states in comparison with the original transiently chaotic neural network.
Clique problem
Clique
Cite
Citations (3)
Clique
Clique problem
Cite
Citations (0)
In this paper, we present an artificial life method of the cellular neural network for max-clique problem. The method is intended to provide an optimum parallel algorithm for solving the max-clique problem. To do this we use the cellular neural network to get a maximum clique. Some of the instances are simulated to verify the proposed method with the simulation results showing that the solution quality is superior to that of best existing parallel algorithm. We also test the learning method on total coloring problem.
Clique
Clique problem
Clique percolation method
Cite
Citations (1)
In this work, we critique two papers, "A Polynomial-Time Solution to the Clique Problem" by Tamta, Pande, and Dhami, and "A Polynomial-Time Algorithm For Solving Clique Problems" by LaPlante. We summarize and analyze both papers, noting that the algorithms presented in both papers are flawed. We conclude that neither author has successfully established that P = NP.
Clique
Clique problem
Cite
Citations (1)
Clique
Clique problem
Bibliography
Cite
Citations (985)
In this paper, the Minimum Nil Sweeper Algorithm, applicable to Clique problem has been considered.It has been found that the Minimum Nil Sweeper Algorithm is not applicable to Clique problem for all undirected graphs which was previously claimed.A new algorithm has been developed to study the all clique problems for arbitrary undirected graph and its complexity is analysed.An experimental result is cited.Finally, the P = NP has been proved for Clique problem.A theorem related to intersection graph is developed.
Clique
Clique problem
NP-complete
Cite
Citations (2)
Clique problem
Clique
Clique percolation method
Clique graph
Split graph
Cite
Citations (1)
Clique problem
Clique
Theory of computation
Cite
Citations (1)
The maximum labelled clique problem is a variant of the maximum clique problem where edges in the graph are given labels, and we are not allowed to use more than a certain number of distinct labels in a solution. We introduce a new branch-and-bound algorithm for the problem, and explain how it may be parallelised. We evaluate an implementation on a set of benchmark instances, and show that it is consistently faster than previously published results, sometimes by four or five orders of magnitude.
Clique problem
Clique
Benchmark (surveying)
Branch and bound
Clique graph
Cite
Citations (0)
Abstract This paper focuses on iterated local search heuristics for the maximum cut‐clique (MCC, or clique neighborhood) problem. Given an undirected graph G = ( V , E ) and a clique C of G , the cut‐clique is the set of edges running between C and V \ C , establishing the cut ( C , V \ C ). The MCC in G is to find a clique with the largest number of edges in the neighborhood of the clique, also known as the maximum edge‐neighborhood clique. This problem has been recently introduced in the literature together with a number of applications, namely, in cell biology instances. However, it has only been addressed so far by exact methods. In this paper, we introduce the first approximate algorithms for tackling the MCC problem, compare the results with the exact methodologies, and explore a new application within marketing analysis, which provide a new alternative perspective for mining market basket problems.
Clique problem
Clique
Heuristics
Clique-sum
Iterated function
Clique graph
Clique percolation method
Split graph
Cite
Citations (7)