Catálogo de publicaciones - libros

We give a randomized algorithm for maximum edge-disjoint paths problem (MEDP) and the minimal total length of MEDP, if the graphs are planar and all terminals lie on the outer face in the order , , ..., , , .... Moreover, if the degree of the graph is bounded by 3, the algorithm becomes deterministic and can also output the number of optimal solutions. On the other hand, we prove that the counting version of these problems are #P-hard even if restricted to planar graphs with maximum degree 3.

Given two integers and with 1 ≤  ≤ , we consider the problem of generating nonisomorphic colored outerplanar graphs with at most vertices, where each outerplanar graph is colored with at most colors. In this paper, we treat outerplanar graphs as rooted outerplane graphs, i.e., plane embeddings with a designated vertex as the root, and propose an efficient algorithm for generating all such colored graphs based on a unique representation of those embeddings. Our algorithm runs in () space and outputs all colored and rooted outerplane graphs without repetition in (1) time per graph.

We consider orthogonal drawings of a plane graph with specified face areas. For a natural number , a -gonal drawing of is an orthogonal drawing such that the outer cycle is drawn as a rectangle and each inner face is drawn as a polygon with at most corners whose area is equal to the specified value. In this paper, we show that several classes of plane graphs have a -gonal drawing with bounded ; A slicing graph has a 10-gonal drawing, a rectangular graph has an 18-gonal drawing and a 3-connected plane graph whose maximum degree is 3 has a 34-gonal drawing. Furthermore, we showed that a 3-connected plane graph whose maximum degree is 4 has an orthogonal drawing such that each inner facial cycle is drawn as a polygon with at most 10 + 34 corners, where is the number of vertices of degree 4 in the cycle .

In the representation approach (TTE) to Computable Analysis those representations of an algebraic or topological structure are of interest, for which the basic predicates and functions become computable. There are, however, natural examples of predicates and functions, which are not computable, even not continuous, for any representations. All these results follow from a simple lemma. In this article we prove this lemma and apply it to a number of examples. In particular we prove that various predicates and functions on computable measure spaces are not continuous for any representations, that means “absolutely non-effective”.

A zero-one sequence ,..., is if the number of ’s such that is at most . The notion generalizes well-known sequences. In complexity, one considers circuits with a limited number of NOT gates, being motivated by the gap in our understanding of monotone versus general circuit complexity, and hoping to better understand the power of NOT gates. In this context, the study of , i.e., circuits with inputs ,..., and outputs ¬,...,¬, is fundamental since an inverter with NOTs can be used to convert a general circuit to one with only NOTs. In particular, if linear-size log-depth inverter with NOTs exists, we do not lose generality by only considering circuits with at most NOTs when we seek superlinear size lower bounds or superlogarithmic depth lower bounds. Markov [JACM1958] showed that the minimum number of NOT gates necessary in an -inverter is ⌈log( + 1)⌉. Beals, Nishino, and Tanaka [SICOMP98–STOC95] gave a construction of an -inverter with size (log), depth (log), and ⌈log( + 1)⌉ NOTs. We give a construction of circuits inverting -tonic sequences with size ((log) ) and depth (log loglog + log) using log + logloglog + (1) NOTs. In particular, for the case where  = (1), our -tonic inverter achieves asymptotically optimal linear size and logarithmic depth. Our construction improves all the parameters of the -tonic inverter by Sato, Amano, and Maruoka [COCOON06] with size (), depth (log), and (log) NOTs. We also give a construction of -tonic achieving linear size and logarithmic depth with loglog + logloglog + (1) NOT gates for the case where  = (1). The following question by Turán remains open: Is the size of any depth-(log) inverter with (log) NOT gates superlinear?

A CNF formula is linear if any distinct clauses in contain at most one common variable. A CNF formula is exact linear if any distinct clauses in contain exactly one common variable. All exact linear formulas are satisfiable [4], and for the class LCNF of linear formulas , the decision problem LSAT remains NP-complete. For the subclasses LCNF of LCNF, in which formulas have only clauses of length at least , the decision problem LSAT remains NP-complete if there exists an unsatisfiable formula in LCNF [3,5]. Therefore, the NP-completeness of for is the question whether there exists an unsatisfiable formula in LCNF. In [3,5], it is shown that both LCNF and LCNF contain unsatisfiable formulas by the constructions of hypergraphs and latin squares. It leaves the open question whether for each  ≥ 5 there is an unsatisfiable formula in LCNF. In this paper, we present a simple and general method to construct minimal unsatisfiable formulas in -LCNF for each  ≥ 3.

M. Alekhnovich et al. have recently proposed a model of algorithms, called BT model, which covers Greedy, Backtracking and Simple Dynamic Programming algorithms and can be further divided into three kinds of fixed, adaptive and fully adaptive ones, and have proved exponential time lower bounds of exact and approximation algorithms under adaptive BT model for Knapsack problem which are about and ((1/))(for approximation ratio 1 − ), respectively (M. Alekhovich, A. Borodin, J. Buresh-Oppenheim, R. Impagliazzo, A. Magen, and T. Pitassi, Toward a Model for Backtracking and Dynamic Programming, , pp308-322, 2005). In this short note, we slightly improve their lower bounds to and ((1/)), respectively, through more complicated combinatorial arguments, and propose as an open question what is the best achievable lower bound for Knapsack problem under the adaptive BT model.

A random multivariate polynomial system with more equations than variables is likely to be unsolvable. On the other hand if there are more variables than equations, the system has at least one solution with high probability. In this paper we study in detail the phase transition between these two regimes, which occurs when the number of equations equals the number of variables. In particular the limiting probability for no solution is 1/ at the phase transition, over a prime field.

We also study the probability of having exactly solutions, with  ≥ 1. In particular, the probability of a unique solution is asymptotically 1/ if the number of equations equals the number of variables. The probability decreases very rapidly if the number of equations increases or decreases.

Our motivation is that many cryptographic systems can be expressed as large multivariate polynomial systems (usually quadratic) over a finite field. Since decoding is unique, the solution of the system must also be unique. Knowing the probability of having exactly one solution may help us to understand more about these cryptographic systems. For example, whether attacks should be evaluated by trying them against random systems depends very much on the likelihood of a unique solution.

We propose polynomial time approximation algorithms for a novel maximum edge coloring problem which arises from the field of wireless mesh networks [8]. The problem is about coloring all the edges in a graph and finding a coloring solution which uses the maximum number of colors with the constraint, for every vertex in the graph, all the edges incident to it are colored with no more than ( ∈ ℤ,  ≥ 2) colors. The case  = 2 is of great importance in practice. In this paper, we design approximation algorithms for cases  = 2 and  > 2 with approximation ratio 2.5 and respectively. The algorithms can give practically usable estimations on the upper bounds of the numbers of the channels used in wireless mesh networks.

We present two new algorithms for range-efficient estimating problem and improve the previously best known result, proposed by Pavan and Tirthapura in [15]. Furthermore, these algorithms presented in our paper also improve the previously best known result for Max-Dominance Norm Problem.