Computer Science – Computational Complexity
Scientific paper
2012-04-20
Computer Science
Computational Complexity
11 pages
Scientific paper
The local minimum degree of a graph is the minimum degree reached by means of a series of local complementations. In this paper, we investigate on this quantity which plays an important role in quantum computation and quantum error correcting codes. First, we show that the local minimum degree of the Paley graph of order p is greater than sqrt{p} - 3/2, which is, up to our knowledge, the highest known bound on an explicit family of graphs. Probabilistic methods allows us to derive the existence of an infinite number of graphs whose local minimum degree is linear in their order with constant 0.189 for graphs in general and 0.110 for bipartite graphs. As regards the computational complexity of the decision problem associated with the local minimum degree, we show that it is NP-complete and that there exists no k-approximation algorithm for this problem for any constant k unless P = NP.
Javelle Jérôme
Mhalla Mehdi
Perdrix Simon
No associations
LandOfFree
On the Minimum Degree up to Local Complementation: Bounds and Complexity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the Minimum Degree up to Local Complementation: Bounds and Complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Minimum Degree up to Local Complementation: Bounds and Complexity will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-5417