The minimization of the spectral radius by removing m links is shown to be an NP-complete problem, which suggests considering heuristic strategies. In this paper several greedy strategies are compared, and several bounds on the decrease of the spectral radius are derived. The strategy that removes that link l = i ~ j with largest product (x1)_i (x1)_j of the components of the eigenvector x1 belonging to the largest adjacency eigenvalue is shown to be superior to other strategies in most cases.
COBISS.SI-ID: 1024376660
This discussion is published in the esteemed general scientific mathematical journal Proc. Lond. Math. Soc. that ranks in A' (ARRS methodology). It solves the hamiltonicity problem for cubic Cayley graphs on groups with respect to genereting sets consisting of an involution, a non-involution of odd order and the inverse of this non-involution.
COBISS.SI-ID: 1024390740
A Boolean function f has to be evaluated for a fixed but unknown choice of the values of the variables. Each variable x of f has an associated cost c(x), which has to be paid to read the value of x. The problem is to design algorithms that evaluate the function querying the values of the variables sequentially while trying to minimize the total cost incurred. The evaluation of the performance of an algorithm is done by employing competitive analysis, i.e., by considering the ratio between what the algorithm pays and the cost of a cheapest set of variables needed to certify the value taken by the function on the given assignment. The problem is related to the well-studied area of decision tree complexity of Boolean functions. Also, algorithms for efficient evaluation of Boolean functions play an important role in several areas, e.g., electrical engineering (the analysis and design of switching networks), artificial intelligence, medicine (testing patients for a disease), automatic diagnosis, reliability theory, game theory, distributed computing systems, just to mention a few. We study the extremal competitive ratio of Boolean function evaluation. We provide the first non-trivial lower and upper bounds for classes of Boolean functions which are not included in the class of monotone Boolean functions. For the particular case of symmetric functions our bounds are matching and we exactly characterize the best possible competitiveness achievable by a deterministic algorithm. Our upper bound is obtained by a simple polynomial time algorithm.
COBISS.SI-ID: 1024267092