Catálogo de publicaciones - libros

In this paper, we study the following minimum rooted star cover problem: given a complete graph  = (, ) with a length function : →ℤ that satisfies the triangle inequality, a designated root vertex  ∈ , and a length bound , the objective is to find a minimum cardinality set of rooted stars, that covers all vertices in such that the length of each rooted star is at most , where a rooted star is a subset of having a common center  ∈  and containing the edge (, ). This problem is -complete and we present a constant ratio approximation algorithm for this problem.

We develop a refinement of a forbidden submatrix characterization of 0/1-matrices fulfilling the Consecutive Ones Property (C1P). This novel characterization finds applications in new polynomial-time approximation algorithms and fixed-parameter tractability results for the problem to find a maximum-size submatrix of a 0/1-matrix such that the submatrix has the C1P. Moreover, we achieve a problem kernelization based on simple data reduction rules and provide several search tree algorithms. Finally, we derive inapproximability results.

The weighted and problems ( ≥ 3) are usually solved through approximation algorithms. In this paper, we define the parameterized versions of these problems and study their algorithms. For the weighted problem, we develop a parameterized algorithm of running time (12.8), which is based on the recently improved color-coding technology and dynamic programming. By refining the techniques, we also develop a more efficient parameterized algorithm of running time (12.8) for the weighted problem, which is a restricted version of the weighted problem.

Kernelizations are an important tool in designing fixed parameter algorithms for parameterized decision problems. We introduce an analogous notion for counting problems, to wit, which turn out to be equivalent to the fixed parameter tractability of counting problems. Furthermore, we study the application of well-known kernelization techniques to counting problems. Among these are the Buss Kernelization and the Crown Rule Reduction for the vertex cover problem. Furthermore, we show how to adapt kernelizations for the hitting set problem on hypergraphs with hyperedges of bounded cardinality and the unique hitting set problem to their counting analogs.

An asynchronous distributed system consisting of a collection of processes interacting via accessing shared services or variables. Failure-tolerant computability for such systems is an important issue, but too little attention has been paid to the case where the services themselves can fail. Recently, it’s proved that consensus problem can’t be (+1)-resiliently solved using a finite number of reliable registers and -resilient services (failure-aware services must be fully connected). We generalize the result in two dimensions. Firstly, it’s shown that the impossibility holds even if infinitely many registers and services are allowed. Secondly, we prove that replacing the reliable registers with reliable shared variables still leave the impossibility to hold, if only failure-oblivious services are allowed.

Given a graph , an integer , and demands set  = {(, ), ..., (, )}, the -Steiner Forest problem finds a forest in graph to connect at least demands in such that the cost of the forest is minimized. This problem is proposed by Hajiaghayi and Jain in SODA’06. Thereafter, using Lagrangian relaxation technique, Segev et al. give the first approximation algorithm to this problem in ESA’06, with performance ratio . We give a new approximation algorithm to this problem with performance ratio via greedy approach, improving the previously best known ratio in the literature.

In [8], a high availability framework based on Harary graph as network topology has been proposed for stateful failover. Framework proposed therein exhibits an interesting property that an uniform load can be given to each non-faulty node while maintaining fault tolerance. A challenging problem in this context, which has not been addressed in [8] is to be able to come up with a distributed algorithm of automated fault recovery which can exploit the properties exhibited by the framework. In this work, we propose a distributed algorithm with low message and round complexity for automated fault recovery in case of stateful failover. We then prove the correctness of the algorithm using techniques from formal verification. The safety, liveness and the timeliness properties of the algorithm have been verified by the model checker SPIN.

We analyze some edge-fault-tolerant properties of the folded hypercube, which is a variant of the hypercube obtained by adding an edge to every pair of nodes with complementary address. We show that an -dimensional folded hypercube is ( − 2)-edge-fault-tolerant Hamiltonian-connected when ( ≥ 2) is even, ( − 1)-edge-fault-tolerant strongly Hamiltonian-laceable when ( ≥ 1) is odd, and ( − 2)-edge-fault-tolerant hyper Hamiltonian-laceable when ( ≥ 3) is odd.

The constrained minimum vertex cover problem on bipartite graphs (the Min-CVCB problem) is an NP-complete problem. This paper presents a polynomial time approximation algorithm for the problem based on the technique of chain implication. For any given constant > 0, if an instance of the Min-CVCB problem has a minimum vertex cover of size (, ), our algorithm constructs a vertex cover of size , satisfying .