Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAn Improved Exact Algorithm for the Domatic Number Problem
67
0
0.0
(
0
)
Added by
Tobias Riege
Publication date
2006
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The 3-domatic number problem asks whether a given graph can be partitioned intothree dominating sets. We prove that this problem can be solved by a deterministic algorithm in time 2.695^n (up to polynomial factors). This result improves the previous bound of 2.8805^n, which is due to Fomin, Grandoni, Pyatkin, and Stepanov. To prove our result, we combine an algorithm by Fomin et al. with Yamamotos algorithm for the satisfiability problem. In addition, we show that the 3-domatic number problem can be solved for graphs G with bounded maximum degree Delta(G) by a randomized algorithm, whose running time is better than the previous bound due to Riege and Rothe whenever Delta(G) >= 5. Our new randomized algorithm employs Schoenings approach to constraint satisfaction problems.
rate research
Read More
The three domatic number problem asks whether a given undirected graph can be partitioned into at least three dominating sets, i.e., sets whose closed neighborhood equals the vertex set of the graph. Since this problem is NP-complete, no polynomial-time algorithm is known for it. The naive deterministic algorithm for this problem runs in time 3^n, up to polynomial factors. In this paper, we design an exact deterministic algorithm for this problem running in time 2.9416^n. Thus, our algorithm can handle problem instances of larger size than the naive algorithm in the same amount of time. We also present another deterministic and a randomized algorithm for this problem that both have an even better performance for graphs with small maximum degree.
We prove that the exa
In this paper, we study the properties of the Frank-Wolfe algorithm to solve the ExactSparse reconstruction problem. We prove that when the dictionary is quasi-incoherent, at each iteration, the Frank-Wolfe algorithm picks up an atom indexed by the support. We also prove that when the dictionary is quasi-incoherent, there exists an iteration beyond which the algorithm converges exponentially fast.
One of the strongest techniques available for showing lower bounds on quantum communication complexity is the logarithm of the approximation rank of the communication matrix--the minimum rank of a matrix which is entrywise close to the communication matrix. This technique has two main drawbacks: it is difficult to compute, and it is not known to lower bound quantum communication complexity with entanglement. Linial and Shraibman recently introduced a norm, called gamma_2^{alpha}, to quantum communication complexity, showing that it can be used to lower bound communication with entanglement. Here the parameter alpha is a measure of approximation which is related to the allowable error probability of the protocol. This bound can be written as a semidefinite program and gives bounds at least as large as many techniques in the literature, although it is smaller than the corresponding alpha-approximation rank, rk_alpha. We show that in fact log gamma_2^{alpha}(A)$ and log rk_{alpha}(A)$ agree up to small factors. As corollaries we obtain a constant factor polynomial time approximation algorithm to the logarithm of approximate rank, and that the logarithm of approximation rank is a lower bound for quantum communication complexity with entanglement.
We present an exact dynamical QCD simulation algorithm for the $O(a)$-improved Wilson fermion with odd number of flavors. Our algorithm is an extension of the non-Hermitian polynomials HMC algorithm proposed by Takaishi and de Forcrand previously. In our algorithm, the systematic errors caused by the polynomial approximation of the inverse of Dirac operator is removed by a noisy-Metropolis test. For one flavor quark it is achieved by taking the square root of the correction matrix explicitly. We test our algorithm for the case of $N_f=1+1$ on a moderately large lattice size ($16^3times48$). The $N_f=2+1$ case is also investigated.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
