Computing and Combinatorics

We prove that the families matrix powering, iterated matrix product, and adjoint matrix are VQP-complete, where VQP denotes Valiant’s class of quasipolynomial-computable families of multivariate polynomials. This proves a conjecture by Bürgisser [3, Conjecture 8.1].

The paper presents a simple construction ofp olynomial length universal traversal sequences for cycles. These universal traversal sequences are log-space (even NC1) constructible and are oflength O(n4.03). Our result improves the previously known upper-bound O(n4.76) for logspace constructible universal traversal sequences for cycles.

A language is universally polynomial if its intersection with every NP-complete language is in P. Such a language would provide an automatic method for generating easy instances of intractable problems. In this note, we give a complete characterization of universally polynomial languages that are context-free, answering an open question in [4].

This paper gives an exponential separation on the depth of branching programs (BPs) between oblivious and non-oblivious BPs. Namely, there is a difference just like the difference between sequential and NC computation: (i) There is a Boolean function f1 of N variables which can be computed by a polynomial-size, syntactic BP with a depth of 2 logN - log logN + 1 but cannot be computed by any oblivious BPs with a depth of (2-ε)N for some ε ∈ o(1). (ii) Similarly, there is an f₂ computed by a syntactic depth of log3N but not by an oblivious depth of Ώ(N logN). (iii) We also show that any (unrestricted) BP of depth t can be simulated by an oblivious BP with a depth of N + ⌈(t - logN)/(log logN + C)⌉·N. The third result implies that f1 cannot be computed by any BP with a depth less than logN +log logN and f2 not with a depth of o(logN·log logN). Note that most bounds in this paper include factors and lower-degree terms.

We prove that a very basic class of program schemes augmented with access to a queue and an additional numeric universe within which counting is permitted accepts exactly the class of recursively solvable problems. The class of problems accepted when access to the numeric universe is removed is exactly the class of recursively solvable problems that are closed under extensions. We build upon NSPQ(1) an in?nite hierarchy of classes of program schemes and show that the class of problems accepted by these program schemes has a zero-one law and consists of those problems de?ned in any vectorized Lindström logic formed using operators whose corresponding problems are recursively solvable and closed under extensions. We apply our results to yield logical characterizations of complexity classes and provide logical analogs to inequalities and hypotheses from complexity theory involving the classes NP through to ELEMENTARY.

Karp and Lipton, in their seminal 1980 paper, introduced the notion of advice (nonuniform) complexity, which since has been of central importance in complexity theory. Nonetheless, much remains unknown about the optimal advice complexity of classes having polynomial advice complexity.In particular, let P-sel denote the class of all P-selective sets [23] For the nondeterministic advice complexity of P-sel, linear upper and lower bounds are known [10]. However, for the deterministic advice complexity of P-sel, the best known upper bound is quadratic [13], and the best known lower bound is the linear lower bound inherited from the nondeterministic case. This paper establishes an algebraic sufficient condition for P-sel to have a linear upper bound: If all P-selective sets are associatively P-selective then the deterministic advice complexity of P-sel is linear. (The weakest previously known sufficient condition was P = NP.) Relatedly, we prove that every associatively P-selective set is commutatively, associatively P-selective.

P-complete problems seem to have no parallel algorithm which runs in polylogarithmic time using a polynomial number of processors. A P-complete problem is in class EP (Efficient and Polynomially fast) if and only if there exists a cost optimal algorithm to solve it in T(n) = O(t(n)€) (€ lt; 1) using P(n) processors such that T(n)×P(n) = O(t(n)), where t(n) is the time complexity of the fastest sequential algorithm which solves the problem. The goal of our research is to find EP parallel algorithms for P-complete problems. In this paper we consider two P-complete geometric problems in the plane. First we consider the convex layers problem of a set S of n points. Let k be the number of the convex layers of S. When 1 = k = n €/2 (0 lt; € lt; 1) we can ?nd the convex layers of S in O( n log n/p ) time using p processors, where 1 = p = n 1-€/2 . Next, we consider the envelope layers problem of a set S of n line segments. Let k be the number of the envelope layers of S. When 1 = k = n€/2 (0 lt; € lt; 1), we propose an algorithm for computing the envelope layers of S in O(na(n) log3np) time using p processors, where 1 = p = n 1-€/2 , and a(n) is the functional inverse of Ackermann’s function which grows extremely slowly. The computational model we use in this paper is the EREW-PRAM. Our ?rst algorithm, for the convex layers problem, belongs to EP, and the second one, for the envelope layers problem, belongs to the class EP if a small factor of log n is ignored.

DNA sequencing by hybridization is potentially a powerful alternative to standard gel electrophoresis techniques.An important aspect of the approach is the design of the probing scheme and of the associated sequence reconstruction algorithm.Recen tly a novel probing scheme, whose performance is within a constant factor of the information theory bound, has settled the issue of asymptotic optimality.Thus, the research focus has shifted to the ?ne tuning of actual performance, with enormous potential for the life sciences.In this paper we discuss a new algorithmic device, called voting upon failure, which, exploiting the knowledge acquired in the course of the sequence reconstruction process, achieves typically a 20% performance improvement over the previous best technique, and comes at 90%-con?dence within a factor 0.5 of the information-theory bound.

We consider a weighted generalization of multiple sequence alignment with sum-of-pair score. Multiple sequence alignment without weights is known to be NP-complete and can be approximated within a constant factor, but it is unknown whether it has a polynomial time approximation scheme. Weighted multiple sequence alignment can be approximated within a factor of O(log2n) where n is the number of sequences.We prove that weighted multiple sequence alignment is MAX SNP-hard and establish a numerical lower bound on its approximability, namely 324/323 - €. This lower bound is obtained already for the simple binary weighted case where the weights are restricted to 0 and 1. Furthermore, we show that weighted multiple sequence alignment and its restriction to binary weights can be approximated exactly to the same degree.

Let Σ be an alphabet and Σn denote the collection of all sequences of length n over Σ. For any s₁ = a₁a₂...a_ja_j+1...a_n, s₂= b₁b₂...b_j b_j+1...b_n € Sn, a recombination of s₁ and s₂ at position j is de?ned as an operation that crosses s₁ and s₂ at position j and generates t₁=a₁a₂...a_jb_j+1...b_n and t₂=b₁b₂...b_ja_j+1... a_n. Denote A and S two collections of sequences. In this paper, we discuss generating A from S by a series of recombinations in minimum number of steps. We present a greedy algorithm for ?nding the optimal recombination evolutionary history from S to any tree A of sequences when |S|=2.

A d-dimensional simplicial mesh is a Delaunay triangulation if the circumsphere of each of its simplices does not contain any vertices inside. A mesh is well-shaped if the maximum aspect ratio of all its simplices is bounded from above by a constant. It is a long-term open problem to generate well-shaped d-dimensional Delaunay meshes for a given polyhedral domain. In this paper, we present a re?nement-based method that generates well-shaped d-dimensional Delaunay meshes for any PLC domain with no small input angles. Furthermore, we show that the generated well-shaped mesh has O(n) d-simplices, where n is the smallest number of d-simplices of any almost-good meshes for the same domain. A mesh is almost-good if each of its simplices has a bounded circumradius to the shortest edge length ratio.

We state the following conjecture: any two planar n-point sets (that agree on the number of convex hull points) can be triangulated in a compatible manner, i.e., such that the resulting two planar graphs are isomorphic. The conjecture is proved true for point sets with at most three interior points. We further exhibit a class of point sets which can be triangulated compatibly with any other set (that satis?es the obvious size and hull restrictions). Finally, we prove that adding a small number of Steiner points (the number of interior points minus two) always allows for compatible triangulations.

Let C be the convex-hull of a set of points S with integral coordinates in the plane. It is well-known that |C| ≤ cD2/3 for some constant c where D is the diameter of S: i.e. the maximum distance between any pair of points in S. It has been shown that c = 7.559.. for an arbitrary S, and c = 3.496.. in the special case when S is a ball centered at the origin in the plane. In this paper we show that c = 12/ 3v 4p2 = 3.524.. is sufficient for an arbitrary set of lattice points S of diameter D in the plane, and |C| ~ 12 3v2/(9p2) D2/3 = 3.388..D2/3 is achieved asymptotically. Our proof is based on the construction of a special set in ?rst quadrant, and the analysis of the result involves the calculation of the average order of certain number-theoretical functions associated with the Euler totient function φ(n).

In this paper we study the following planar two-watchtower problem: given a terrain (X-monotone chain) T with n vertices, locate two vertical segments (watchtowers) /uv and /u′v′ which have to be erected on T such that every point on T is visible to the top of either watchtowers (u or u′) and the maximum height of /uv, /u′v′ is minimized. We present an O(n4) time algorithm to solve the discrete version of this problem when v, v′ must be on some vertices of T. Under a mild condition on solving a special cubic equation with three bounded variables in O(f3) time we can also generalize the algorithm to solve the general problem in O(n4 +n3f₃) time. Using parametric search, the discrete problem can be solvedin O(n3 log2n) time and the general problem can be solved in O(n4 log2n) time.

A “rooted” plane triangulation is a plane triangulation with one designated vertex on the outer face. In this paper we give a simple algorithm to generate all triconnected rooted plane triangulations with at most n vertices. The algorithm uses O(n) space and generates such triangulations in O(1) time per triangulation without duplications. The algorithm does not output entire triangulations but the difference from the previous triangulation. By modifying the algorithm we can generate all triconnected rooted plane triangulation having exactly n vertices including exactly r vertices on the outer face in O(r) time per triangulation without duplications, while the previous best algorithm generates such triangulations in O(n2) time per triangulation. Also we can generate without duplications all triconnected (non-rooted) plane triangulations having exactly n vertices including exactly r vertices on the outer face in O(r2n) time per triangulation, and all maximal planar graphs in O(n3) time per graph.

We consider the following problem. Given a polygon P, possibly with holes, and having n vertices, compute a pair of equal radius disks that do not intersect each other, are contained in P, and whose radius is maximized. Our main result is a simple randomized algorithm whose expected running time, on worst case input, is O(n log n). This is optimal in the algebraic decision tree model of computation.

In this paper, we consider the problem of computing a maximum cardinality matching among a set I of n intervals that are colored as either red or blue, such that a pair of intervals in I can be matched only if they overlap with each other and have different colors. This problem arises in some applications such as radiosurgery treatment planning. We present a greedy algorithm for this problem that runs in O(n log log n) time for sorted input.We also solve a useful generalization of this red/blue interval matching problem in the same time bound.

Let N be a set of n points in convex position in ∝3. The farthest-point Voronoi diagram of N partitions ∝3 into n convex cells. We consider the intersection G(N) of the diagram with the boundary of the convex hull of N. We give an algorithm that computes an implicit representation of G(N) in expected O(n log2n) time. More precisely, we compute the combinatorial structure of G(N), the coordinates of its vertices, and the equation of the plane de?ning each edge of G(N). The algorithm allows us to solve the all-pairs farthest neighbor problem for N in expected time O(n log2n), and to perform farthest-neighbor queries on N in O(log2n) time with high probability. This can be applied to find a Euclidean maximum spanning tree and a diameter 2-clustering of N in expected O(n log4n) time.

Let π(a, b)denote the shortest path between two points a, b inside a simple polygon P, which totally lies in P. The geodesic distance between a and b in P is defined as the length of π(a, b), denoted by gd(a, b), in contrast with the Euclidean distance between a and b, denoted by d(a, b). Given two disjoint polygons P and Q in the plane, the bridge problem asks for a line segment (optimal bridge)that connects a point p on the boundary of P and a point q on the boundary of Q such that the sum of three distances gd(p′, p), d(p, q)and gd(q, q′), with any p′ € P and any q′ € Q, is minimized. We present an O(n log3n)time algorithm for finding an optimal bridge between two simple polygons. This significantly improves upon the previous O(n2)time bound.

Generating high quality meshes is one of the most important steps in many applications such as scientific computing. Sink insertion method is one of the mesh quality improvement methods that had been proposed recently. However, it is unknown whether this method is competitive to generate meshes with small number of elements. In this paper, we show that, given a two-dimensional polygonal domain with no small angles, the sink insertion method generates a well-shaped mesh with O(n) triangles, where n is the minimum number of triangles generated by any method with the same quality guarantee.We also show that the sink insertion method more likely can not guarantee the same result for a three-dimensional domain, while the other methods such as Delaunay refinement can achieve.

In this paper, we present an O(n3 log n) time solution for the following multi-label map labeling problem: Given a set S of n distinct sites in the plane, place at each site a triple of uniform squares of maximum possible size such that all the squares are axis-parallel and a site is on the boundaries of its three labeling squares. We also study the problem under the discrete model, i.e., a site must be at the corners of its three label squares. We obtain an optimal ΘT(n log n) time algorithm for the latter problem.

Given a simple polygon P with n vertices and a starting point s on its boundary, the watchman route problem asks for a shortest route in P through s such that each point in the interior of the polygon can be seen from at least one point along the route.It is known that the watchman route problem can be reduced in O (n log n )time to that of computing the shortest route which visits a set of line segments in polygon P .In this paper,we present a simple approximation algorithm for computing the shortest route visiting that set of line segments. Our algorithm runs in O(n)time and produces a watchman route of at most 2 times the length of the shortest watchman route.The best known algorithm for computing the shortest watchman through s takes O(n4)time [3]. Our scheme is also employed to give a √2-approximation solution to the zookeeper’s problem, which is a variant of the watchman route problem.

A data structure called PC-tree is introduced as a generalization of PQ-trees. PC-trees were originally introduced in a planarity test of Shih and Hsu where they represent partial embeddings of planar graphs. PQ-trees were invented by Booth and Lueker to test the consecutive ones property in matrices. The original implementation of the PQ-tree algorithms by Booth and Lueker using nine templates in each bottom-up iteration is rather complicated. Also the complexity analysis is rather intricate. We give a very simple PC-tree algorithm with the following advantages: (1) it does not use any template; (2) it does all necessary operations at each iteration in one batch and does not involve the cumbersome bottom-up operation PC-trees can be used naturally to test the circular ones property in matrices. And the induced PQ-tree algorithm can considerably simplify Booth and Lueker’s modification of Lempel, Even and Cederbaum’s planarity test.

We investigate the relative efficiency of a finite number of stacks in comparison to several variants of deques. In the nondeterministic setting, two stacks can simulate a general deque in linear time. This implies a negative answer to the question raised by Brandenburg whether a deque can simulate a finite number of tapes in linear time. Wealso show that in realtime an output-restricted deque cannot simulate two stacks for deterministic computations. It is known that a general deque can be simulated deterministically by three stacks in linear time. We describe an approach that is simpler to analyze and has a smaller constant factor (with respect to the required stack operations) than a previous solution.

We refine and optimize a computationally intensive enumeration method, based on the traversal of a quadtree, for finding lower bounds on the lengths of reflecting sequences for labeled chains. The improvement results from the introduction of a redundancy relation defined on vertex-pairs of the underlying quadtree, which enables the pruning of redundant branches near the root of the quadtree, as well as locally at deeper depths. The test run of the implementation showed a length lower bound of 19t-214 for t-reflecting sequences for labeled 7-chains with significant speedup, which yields the current length lower bound Ώ(n1.51) for universal traversal sequences for 2-regular graphs of n vertices, and Ώ(d2-1.51n2.51) for universal traversal sequences for d-regular graphs of n vertices, where 3 ≤ d ≤ n/17 + 1.

We consider a competitive facility location problem with two players.Pla yers alternate placing points, one at a time, into the playing arena, until each of them has placed n points.The arena is then subdivided according to the nearest-neighbor rule, and the player whose points control the larger area wins.We present a winning strategy for the second player, where the arena is a circle or a line segment.

Let Γ = (N, v) be a cooperative game with the player set N and characteristic function v: 2N → R. An imputation of the game is in the core if no subset of players could gain advantage by splitting from the grand coalition of all players. It is well known that, for the linear production game, and the flow game, the core is always non-empty (and a solution in the core can be found in polynomial time). In this paper, we show that, given an imputation x, it is NP-complete to decide it is not a member of the core, in both games. The same also holds for Steiner tree game. In addition, for Steiner tree games, we prove that testing the total balacedness is NP-hard.

This work proposes two identification algorithms based on some difficult problems. The first scheme is an extremely simple combination of the idea of one-time passwords and the use of public keys. The second proposal allows identification to be implemented without leaking any secret information during the interaction because it combines the two mentioned concepts with a zero-knowledge proof of the possession of a solution to a difficult graph problem through a challenge-response technique.

This paper presents a new exponentiation architecture and multiplier/squarer for GF(2m), which uses a standard basis representation. The proposed multiplier/squarer is used as kernel architecture of exponentiation. Although the proposed multiplier/squarer computes the multiplication and squaring operations at the same time in GF(2m), the common parts existing in both operations are only executed once, thereby reducing the required hardware compared to related systolic circuits. The proposed multiplier/squarer can be easily applied to exponentiation architecture. It is also well suited to VLSI implementation because of its regularity, modularity, and unidirectional data flow.

We present a simple space saving trick that applies to many previous algorithms for transitive closure and shortest paths in dynamic directed graphs. In these problems, an update can change all edges incident to a node.The basic queries on reachability and distances should be answered in constant time, but also paths should be produced in time proportional to their length. For: Transitive closure of Demetrescu and Italiano (FOCS 2000) Space reduction from O(n3) to O(n2), preserving an amortized update time of O(n2).Exact all-pairs shortest dipaths of King (FOCS 1999) Space reduction from Ō(n3) to Ō(n2vnb), preserving an amortized update time of Ō(n2vnb), where b is the maximal edge weight.Approximate all-pairs shortest dipaths of King (FOCS 1999) Space reduction from Ō(n3) to Ō(n2), preserving an amortized update time of Ō(n2). Several authors (Demetrescu and Italiano, FOCS 2000, and Brown and King, Oberwolfach 2000) had discovered techniques to give a corresponding space reduction, but these techniques could be used to show only the existence of a desired dipath, and could not be used to produce the actual path.

In an undirected, 2-node connected graph G = (V,E) with positive real edge lengths, the distance between any two nodes r and s is the length of a shortest path between r and s in G. The removal of a node and its incident edges from G mayincrease the distance from r to s. A most vital node of a given shortest path from r to s is a node (other than r and s) whose removal from G results in the largest increase of the distance from r to s. In the past, the problem of finding a most vital node of a given shortest path has been studied because of its implications in network management, where it is important to know in advance which component failure will affect network efficiency the most. In this paper, we show that this problem can be solved in O(m + n log n) time and O(m) space, where m and n denote the number of edges and the number of nodes in G.

Let C be a set of colors, and let ω be a cost function which assigns a real number ω(c) to each color c in C. An edge-coloring of a graph G is to color all the edges of G so that any two adjacent edges are colored with different colors. In this paper we give an efficient algorithm to find an optimal edge-coloring of a given tree T, that is, an edgecoloring f of T such that the sum of costs ω(f(e)) of colors f(e) assigned to all edges e is minimum among all edge-colorings of T. The algorithm takes time O(nΔ2) if n is the number of vertices and Δ is the maximum degree of T.

The problem of counting all H-colorings of a graph G of n vertices is considered. While the problem is, in general, #P-complete, we give linear time algorithms that solve the main variants of this problem when the input graph G is a k-tree or, in the case where G is directed, when the underlying graph of G is a k-tree. Our algorithms remain polynomial even in the case where k = O(log n) or in the case where the size of H is O(n). Our results are easy to implement and imply the existence of polynomial time algorithms for a series of problems on partial k-trees such as core checking and chromatic polynomial computation.

We give O(m+ n) algorithms for enumerating all minimum separators as well as minimal separators in a connected chordal graph. We give a tight upper bound, n - κ(G) - 1, for the number of minimal separators in a chordal graph. An important contribution of the paper is our characterisation of minimal (minimum) separators of chordal graphs and the above results are obtained as consequences of the characterisations.

Graph separation is a well-known tool to make (hard) graph problems accessible for a divide and conquer approach. We show how to use graph separator theorems in order to develop fixed parameter algorithms for many well-known NP-hard (planar) graph problems. We coin the key notion of glueable select&verify graph problems and derive from that a prospective way to easily check whether a planar graph problem will allow for a fixed parameter divide and conquer algorithm of running time c$$ ^{\sqrt k } $$ · nO(1) for a constant c.

For a graph G on n vertices, with positive integer weights w₁,...,w_n assigned to the n vertices such that, for every clique K of G, $$ \sum\limits_{i \in K} {\frac{1} {{2^{w_i } }}} \leqslant 1 $$, the problem we are interested in is to assign binary codes C1,...,C_n to the vertices such that C_i has w_i (or a function of w_i) bits in it and, for every edge i, j, C_i and C_j are not prefixes of each other.We call this the Graph Prefix Free Code Assignment Problem. We relate this new problem to the problem of designing adversaries for comparison based sorting algorithms. We show that the decision version of this problem is as hard as graph colouring and then present results on the existence of these codes for prefect graphs and its subclasses.

One of the most important problem in computational biology is the tree editing problem which is to determine the edit distance between two rooted labeled trees. It has been shown to have significant applications in both RNA secondary structures and evolutionary trees. Another viewpoint of considering this problem is to find an edit mapping with the minimum cost. By restricting the type of mapping, Zhang [7,8] and Richter [5] independently introduced the constrained edit distance and the structure respecting distance, respectively. They are, in fact, the same concept. In this paper, we define a new measure of the edit distance between two rooted labeled trees, called less-constrained edit distance, by relaxing the restriction of constrained edit mapping. Then we study the algorithmic complexities of computing the less-constrained edit distance between two rooted labeled trees. For unordered labeled trees, we show that this problem is NP-complete and even has no absolute approximation algorithm unless P = NP, which also implies that it is impossible to have a PTAS for the problem. For ordered labeled trees, we give a polynomial-time algorithm to solve the problem.

In this paper, we show a necessary and sufficient condition which characterizes all bicritical graphs. Using this necessary and sufficient condition we develop a highly efficient algorithm to determine whether a graph is bicritical, of which the time complexity is bounded by O (|V| |E|), and this is the best result that has ever been known.

We study the problem of producing hierarchical drawings of layered graphs when some pairs of edges are not allowed to cross.We show that deciding on the existence of a drawing satisfying at least k constraints from a given set of non-crossing constraints is NP-complete even if the graph is 2-layered and even when the permutation of the vertices on one side of the bipartition is fixed.W e also propose simple constant-ratio approximation algorithms for the optimization version of the problem and we discuss how to extend the well-known hierarchical approach for creating layered drawings of directed graphs with the capability of minimizing the number of edge crossings while maximizing the number of satisfied non-crossing constraints.

Hierarchical decompositions are a useful tool for drawing large graphs. Such decompositions can be represented by means of a data structure called hierarchy tree. In this paper we introduce the notion of P-validity of hierarchy trees with respect to a given property P: this notion reflects the similarity between the topological structure of the original graph and of any high-level representation of it obtained from the hierarchy tree. We study the P-validity when the clustered graph is a tree and property P is the acyclicity, presenting a structure theorem for the P-validity of hierarchy trees under these hypotheses.

A three-valued function f defined on the vertex set of a graph G = (V,E), f: V → -1, 0, 1 is a minus dominating function if the sum of its function values over any closed neighborhood is at least one. That is, for every v € V, f(N[v]) = 1, where N[v] consists of v and all vertices adjacent to v. The weight of a minus function is $$ f\left( V \right) = \sum _{\upsilon \in V} f\left( \upsilon \right) $$. The minus domination number of a graph G, denoted by γ-(G),equals the minimum weight of a minus dominating function of G. In this paper,sharp lower bounds on minus domination of a bipartite graph are given. Thus, we prove a conjecture proposed by J. Dunbar etc.(Discrete Math. 199(1999) 35-47), and we give a lower bound on γ_ka(G) of a graph G.

It is well known that in a graph, κ(G)≤λ(G) ≤ δ(G), where κ (G), δ(G) and d(G) denote the vertex connectivity, edge connectivity and the minimum degree of G, respectively. We show that in chordal graphs, if (G) ≠ d(G), then (G) = 2_?(G) - 1. In contrast, in a general graph (G) can be equal to (G).

Graham and Harary [3]studied how the diameter of hypercubes can be affected by increasing and decreasing edges. Since many networks are constructed by graph products, e.g., tori and meshes, in this paper we study how the diameter of graph products, particularly Cartesian product and Kronecker product, can be changed by adding and removal of edges. We study Cartesian products on paths, cycles, trees, and hypercubes. The diameter of the Kronecker product of two graphs is in general difficult to find. We in particular study the Kronecker product of two cycles.

All vertex-sets of cliques of G form the simplexes of an abstract complex C(G), which is called the clique complex of G. It is proved that the clique complex of a plane graph G is acyclic if and only if G is contractible.

This work deals with the domination numbers of generalized de Bruijn digraphs and generalized Kautz digraphs. Dominating sets for digraphs are not familiar compared with dominating set for undirected graphs. Whereas dominating sets for digraphs have more applications than undirected graphs. We construct dominating sets of generalized de Bruijn digraphs under some conditions. We investigate consecutive minimum dominating set of the generalized de Bruijn digraphs. For generalized Kautz digraphs, there is a consecutive minimum dominating set that is a minimum dominating set.

In this note, we consider four quantities defined on a bipartite graph B: the cross-chromatic index χ*(B), the biclique number w*(B),the cross-free matching number m*(B) and the biclique edge covering number ß*(B). We mention several applications of these numbers and define a notion of cross-perfect bipartite graphs. A duality between these numbers for the class of cross-perfect graphs is examined.

Consider a graph G = (V,E) with an [a, b]-factorization F = F₁, F₂,..., F_m.It is proved in this paper that: 1.there is an m-matching of G to which F is orthogonal if n = V (G)2.if $$ \sqrt {2b} \leqslant a \leqslant b $$, then for any given edge e of G,there is a [1, a]-subgraph H of G such that e is included in H and F is orthogonal to H.

In a systematic erasure code for the correction of two simultaneous erasures, each information symbol must have two associated parity symbols. When implemented in a redundant array of independent disks (RAID), performance requirements on the update penalty necessitate that each information symbol be associated with no more parity symbols than the two required. This leads to a simple graph model of the erasure codes, with parity symbols as vertices and information symbols as edges. Ordering the edges so that no more than f check disks (vertices) appear amongan y set of d consecutive edges is found to optimize access performance of the disk array when d is maximized. These cluttered orderings are examined for the complete graph K_n. The maximum number d of edges is determined precisely when f ≤ 5 and when f = n - 1, and bounds are derived in the remainingcases.

Stream merging is a promising technique for reducing server bandwidth in video-on-demand systems. There are many heuristics for the problem proposed whose effectiveness has been confirmed empirically. However, it is desirable to prove their effectiveness mathematically. In the pioneering work [2], Bar-Noy and Ladner studied stream merging using competitive analysis. They designed an O(log n)-competitive online scheduler, where n is the totaln umber of stream requests. However, their result is applicable only to systems with large client bandwidth and buffer size. In this paper we design the first on-line scheduler for stream merging in the general setting, in which we lift the large resource requirements, and our scheduler achieves constant competitive ratio.

We consider an on-line non-preemptive deadline scheduling on multiple resources. Each job has the slack time during which it can wait until its expiration time, the last time it can be started to be completed by the deadline. There are a number of resources on which the jobs are allocated. The effect of slack times on the on-line deadline scheduling was investigated in [8] by analyzing the performance of the Earliest EXpiration Time First (EXF) algorithm. But most of the previous work is restricted to a single resource, and in this paper, we propose a different method of analysis which can also be applied to multiple resources. So we can extend the result of [8] to multiple resources.

Motivated by an application in thin wire visualization, we study an abstract on-line scheduling problem. Unlike most scheduling problems, our schedulers can gain partial merit from a partially served request. Thus our problem embodies a notion of “Level of Service” that is increasingly important in multimedia applications. We give two schedulers FirstFit and EndFit based on two simple heuristics, and generalize them into a class of greedy schedulers. We show that both FirstFit and EndFit are 2-competitive, and any greedy scheduler is 3-competitive. These bounds are shown to be tight.

We consider one-dimensional and multi-dimensional vector covering with variable sized bins.In the one-dimensional case, we consider variable sized bin covering with bounded item sizes. For every finite set of bins B, and upper bound 1/m on the size of items for some integer m, we define a ratio r(B,m). We prove this is the best possible competitive ratio for the set of bins B and the parameter m, by giving both an algorithm with competitive ratio r(B,m), and an upper bound of r(B,m) on the competitive ratio of any on-line deterministic or randomized algorithm. The ratio satisfies r(B,m) ≥ m/(m + 1), and equals this number if all bins are of size 1. For multi-dimensional vector covering we consider the case where each bin is a binary d-dimensional vector. It is known that if B contains a single bin which is all 1, then the best competitive ratio is T(1/d). We show an upper bound of 1/2d(1-o(1)) for the general problem, and consider four special case variants. We show an algorithm with optimal competitive ratio 1/2 for the model where each bin in B is a unit vector. We consider the model where B consists of all unit prefix vectors. Each bin has i leftmost components of 1, and all other components are 0. We show that this model is harder than the case of unit vector bins, by giving an upper bound of O(1/log d) on the competitive ratio of any deterministic or randomized algorithm. Next, we discuss the model where B contains all binary vectors. We show this model is easier than the model of one bin type which is all 1, by giving an algorithm of ratio O(1/log d).The most interesting multi-dimensional case is d = 2. Previous results give a 0.25-competitive algorithm for B = (1,1), and an upper bound of 0.4 on the competitive ratio of any algorithm. In this paper we consider all other models for d = 2. For unit vectors, we give an optimal algorithm with competitive ratio 1/2. For unit prefix vectors we give an upper bound of 4/9 on the competitive ratio of any deterministic or randomized algorithm. For the model where B consists of all binary vectors, we design an algorithm with ratio larger than 0.4. These results show that all above relations between models hold for d = 2 as well.

We consider a general methodology proposed by Chen and Kao [4] for testing polynomial identities.We prove that the test cannot be completely derandomized by any specified set of rational approximations to algebraic numbers up to a polynomial number of bits. The proof is a direct application of Dirichlet’s box principle. We also give some number theoretic estimates for the likelihood of a multiplicatively independent sequence of integers which can be used in their algorithm.

We present an O(n log4n)-time randomized algorithm for gossiping in radio networks with unknown topology. This is the first algorithm for gossiping in this model whose running time is only a polylogarithmic factor away from the optimum. The fastest previously known (deterministic) algorithm for this problem works in time O(n3/2 log2n).

Grover’s quantum search algorithm finds one of t solutions in N candidates by using (π/4)$$ \sqrt {{N \mathord{\left/ {\vphantom {N t}} \right. \kern-\nulldelimiterspace} t}} $$basic steps. It is, however, necessary to know the number t of solutions in advance for using the Grover’s algorithm directly. On the other hand, Boyer etal proposed a randomized application of Grover’s algorithm, which runs, on average, in Oi($$ \sqrt {{N \mathord{\left/ {\vphantom {N t}} \right. \kern-\nulldelimiterspace} t}} $$) basic steps (more precisely, (9/4)$$ \sqrt {{N \mathord{\left/ {\vphantom {N t}} \right. \kern-\nulldelimiterspace} t}} $$ steps) without knowing t in advance. Here we show a simple (almost trivial) deterministic application of Grover’s algorithm also works and finds a solution in O$$ \sqrt {{N \mathord{\left/ {\vphantom {N t}} \right. \kern-\nulldelimiterspace} t}} $$) basic steps (more precisely, (8π/3)$$ \sqrt {{N \mathord{\left/ {\vphantom {N t}} \right. \kern-\nulldelimiterspace} t}} $$ steps) on average.

MAX SAT is one of famous combinatorial optimization problems stated as follows: given a multiset of clauses, find an assignment that maximizes the number of satisfied clauses (that is equivalent to finding an assignment that minimizes the number of unsatisfied clauses). MAX 3SAT is restricted version of MAX SAT, that is, its input is restricted to a multiset of 3-clauses, i.e., each clause contains exactly 3 literals whose underlying variables are distinct each other. Since these problems are not only NP-hard problem, but MAX SNP-complete problem, there is no polynomial time approximation algorithm whose approximation ratio is close to 1 unless P = NP. Furthermore, Håstad showed that it is NP-hard to approximate MAX 3SAT within 8/7 - ε for any eε > 0 [5]. In spite of these negative results, many polynomial time approximation algorithms with proven approximation ratio for MAX SAT have been proposed [3,4,7].

We study variations of Steiner tree problem. Let P = ·p1, p2, ...,p_n× be a set of n terminals in the Euclidean plane. For a positive integer k, the bottleneck Steiner tree problem (BSTP for short) is to find a Steiner tree with at most k Steiner points such that the length of the longest edges in the tree is minimized. For a positive constant R, the Steiner tree problem with minimum number of Steiner points (STP - MSP for short) asks for a Steiner tree such that each edge in the tree has length at most R and the number of Steiner points is minimized.In this paper, we give (1) a ratio-$$ \sqrt 3 + \varepsilon $$ approximation algorithm for BSTP, where € is an arbitrary positive number(2) a ratio-3 approximation algorithm for STP-MSP with running time O(n3);(3)a ratio-52 approximation algorithm for STP-MSP

In this paper, we study the problem of computing a minimum cost Steiner tree subject to weight constraint in a series-parallel graph where each edge has a nonnegative integer cost and a nonnegative integer weight.We present a fully polynomial time approximation scheme for this NP-complete problem.

We consider generalized discrete timed automata with general linear relations over clocks and parameterized constants as clock constraints and with parameterized durations. We look at three approximation techniques (i.e., the r-reset-bounded approximation, the B-bounded approximation, and the 〈B, r〉-crossing-bounded approximation), and derive automata-theoretic characterizations of the binary reachability under these approximations. The characterizations allow us to show that the safety analysis problem is decidable for generalized discrete timed automata with unit durations and for deterministic generalized discrete timed automata with parameterized durations. An example specification written in ASTRAL is used to run a number of experiments using one of the approximation techniques.

In contrast to the adoption of linear additive query updating techniques in existing popular algorithms for user preference retrieval, in this paper we design two types of algorithms, the multiplicative adaptive query expansion algorithm MA and the multiplicative adaptive gradient search algorithm MG, both of which use multiplicative query expansion strategies to adaptively improve the query vector. We prove that algorithm MA has a substantially better mistake bound than the Rocchio’s and the Perceptron algorithms in learning a user preference relation determined by a linear classifier with a small number of non-zero coefficients over the real-valued vector space [0, 1]n.We also show that algorithm MG boosts the usefulness of an index term exponentially, while the gradient descent procedure does so linearly. Our work also generalize the algorithm Winnow in the following aspects: various updating functions may be used; multiplicative updating for a weight is dependent on the value of the corresponding index term, which is more realistic and applicable to real-valued vector space; and finally, a number of documents which may or may not be counterexamples to the algorithm’s current classification are allowed. Practical implementations of algorithms MA and MG have been underway in the next stage development of our intelligent web search tools.

The problem of parametric scheduling is concerned with checking whether a job-set is parametrically schedulable, subject to a set of imposed constraints. In real-time scheduling, parameterization of the schedule plays an important role in extending the flexibility of the scheduler, particularly in the presence of variable execution times. It has been shown that the existence of parametric schedules can be determined in polynomial time when the constraints are restricted to those that can be represented by a network, unimodular matrix. In this paper, we extend the class of constraints for which parametric schedules can be determined efficiently to include network constraints, such as weighted sum of completion times.

The issue of knowledge sharing has been an important topic in multi-agent research. Knowledge sharing leads to that agents analyze, judge and synthesize the told information so as to make agents’ own knowledge. To match these applications, this paper builds a logical framework for knowledge sharing among agents. We developa multimodal logic for reasoning about both agents’ knowledge and told information. For formalizing the relationshipb etween knowledge and told information, we present a framework of semantics, with respect to which a sound and complete proof theory is given.

We propose a lockout avoidance algorithm for the k-exclusion problem on the asynchronous multi-writer/reader shared memory model. This algorithm is the extension of an accelerated version of the n-process algorithm to the k-exclusion problem. The running time by the algorithm for the trying region of any faultless process is bounded by (n - k)c + O(n(n - k)2)l if the number of stopping process failures is less than k, where n is the number of processes, l is an upper bound on the time between two successive atomic steps for any faultless process, and c is an upper bound on the time that any user spends in the criticalregion.

We study prefix-free presentations of computably enumerable reals. In 2, Calude et. al. proved that a real a is c.e. if and only if there is an infinite, computably enumerable prefix-free set V such that $$ \alpha = \sum _{\sigma \in V} 2^{ - \left| \sigma \right|} $$. Following Downey and LaForte 5, we call V a prefixfree presentation of a. Each computably enumerable real has a computable presentation. Say that a c.e. real a is simple if each presentation of a is computable. Downey and LaForte 5 proved that simple reals locate on every jump class. In this paper, we prove that there is a noncomputable c.e. degree bounding no noncomputable simple reals. Thus, simple reals are not dense in the structure of computably enumerable degrees.

Let C_sc and C_wc be classes of the semi-computable and weakly computable real numbers, respectively, which are discussed by Weihrauch and Zheng 12. In this paper we show that both C_sc and C_wc are not closed under the total computable real functions of finite length on some closed interval, although such functions map always a semi-computable real numbers to a weakly computable one. On the other hand, their closures under general total computable real functions are the same and are in fact an algebraic field. This field can also be characterized by the limits of computable sequences of rational numbers with some special converging properties.

We study Turing computability of the nonlinear solution operator S of the Cauchy problem for the Schrödinger equation of the form $$ i\frac{{du}} {{dt}} = - \frac{{d^2 u}} {{dx^2 }} + mu + \left| u \right|^2 u $$ in ℝ.We prove that S is a computable operator from H1(ℝ) to C(ℝH1(ℝ))with respect to the canonical representations.