Search

Many real-life scheduling, routing and location problems can be formulated as combinatorial optimization problems whose goal is to find a linear layout of an input graph in such a way that the number of edge crossings is minimized. In this paper, we study a restricted version of the linear layout problem where the order of vertices on the line is fixed, the so-called fixed linear crossing number problem (FLCNP). We show that this $\mathcal{NP}$-hard problem can be reduced to the well-known maximum cut problem. The latter problem was intensively studied in the literature; efficient exact algorithms based on the branch-and-cut technique have been developed. By an experimental evaluation on a variety of graphs, we show that using this reduction for solving FLCNP compares favorably to earlier branch-and-bound algorithms. [ABSTRACT FROM AUTHOR]

We present an efficient reduction mapping undirected graphs G with n = 2k vertices for integers k to tables of partially specified Boolean functions g: {0,1}4k+1 →{0,1,⊥} so that for any integer m, G has a vertex colouring using m colours if and only if g has a consistent ordered binary decision diagram with at most (2m + 2)n2 + 4n decision nodes. From this it follows that the problem of finding a minimum-sized consistent OBDD for an incompletely specified truth table is NP-hard and also hard to approximate. [ABSTRACT FROM AUTHOR]

Several studies have reported that the linear program relaxation of integer multi-commodity network flow problems often provides integer optimal solutions. We explore this phenomenon with a 0-1 multi-commodity network with mutual arc capacity constraints. Characteristics of basic solutions in the linear programming relaxation problem of the 0-1 multi-commodity problem are identified. Specifically, necessary conditions for a linear programming relaxation to have a non-integer solution are presented. Based on the observed characteristics, a simple illustrative example problem is constructed to show that its LP relaxation problem has integer optimal solutions with a relatively high probability. Furthermore, to investigate whether or not and under what conditions this tendency applies to large-sized problems, we have carried out computational experiments by using randomly generated problem instances. The results of our computational experiment indicate that there exists a narrow band of arc density in which the 0-1 multi-commodity problems possess no integer optimal solutions. [ABSTRACT FROM AUTHOR]

We consider the problem of drawing a directed graph in two dimensions with a minimum number of crossings such that for every node the incoming edges appear consecutively in the cyclic adjacency lists. We show how to adapt the planarization method and the recently devised exact crossing minimization approach in a simple way. We report experimental results on the increase in the number of crossings involved by this additional restriction on the set of feasible drawings. It turns out that this increase is negligible for most practical instances. [ABSTRACT FROM AUTHOR]

Kolmogorov introduced a combinatorial measure of the information I(x : y) about the unknown value of a variable y conveyed by an input variable x taking a given value x. The paper extends this definition of information to a more general setting where ‘x = x′ may provide a vaguer description of the possible value of y. As an application, the space ${\cal P}(\{0,1\}^n)$ of classes of binary functions f:[n]→{0,1}, [n] = {1..., n}, is considered where y represents an unknown function t∈{0,1}[n] and as input, two extreme cases are considered: $\mathsf{x} = x_{{\mathcal M}_d}$ and $\mathsf{x} = x_{{\mathcal M}_d}$ which indicate that t is an element of a set $G\subseteq\{0,1\}^n$ that satisfies a property ${\mathcal M}_d$ or ${\mathcal M}_d$ respectively. Property ${\mathcal M}_d$ (or ${\mathcal M}_d$) means that there exists an $E\subseteq[n]$, E = d, such that trE(G) = 1 (or 2d) where trE(G) denotes the trace of G on E. Estimates of the information value $I(x_{{\mathcal M}_d}:t)$ and $I(x_{{\mathcal M}_d}:t)$ are obtained. When d is fixed, it is shown that $I(x_{{\mathcal M}_d}:t)\approx d$ and $I(x_{{\mathcal M}_d}:t)\approx 1$ as n→∞. Keywords: Information theory, combinatorial complexity, VC-dimension. [ABSTRACT FROM AUTHOR]

Given a pair of integers 2≤s ≤k, define gs(k) to be the minimum integer such that, for any regular multiple hypergraph H =({1..., k}, {e1..., em}) with edge size at most s, there is a permutation π on {1..., m} (or edge ordering eπ(1)..., eπ(m)) such that $g(H, \pi) =\max\{ \max \{d_{H_j}(u) - d_{H_j}(v) : u, v\in e_{\pi(j+1)}\} : j = 0, \dots, m-1\} \le g_s(k)$, where Hj = ({1..., k}, {eπ(1)..., eπ(j)}). The so-called edge ordering problem is to determine the value of gs(k) and to find a permutation π such that g(H, π)≤gs(k). This problem was raised from a switch box design problem, where the value of gs(k) can be used to design hyper-universal switch boxes and an edge ordering algorithm leads to a routing algorithm. In this paper, we show that (1) g2(k) = 1 for all k≥3, (2) gs(k) = 1 for 3≤s≤k≤6, and (3) gs(k) ≤2k for all k≥7. We give a heuristic algorithm for the edge ordering and conjecture that there is a constant C such that gs(k) ≤C for all k and s. [ABSTRACT FROM AUTHOR]

Inferring a graph from path frequency has been studied as an important problem which has a potential application to drug design. Given a multiple set g of strings of labels with length at most K, the problem asks to find a vertex-labeled graph G that attains a one-to-one correspondence between g and the set of sequences of labels along all paths of length at most K in G. In this paper, we prove that the problem with K=1 can be formulated as a problem of finding a loopless and connected detachment, based on which an efficient algorithm for solving the problem is derived. Our algorithm also solves the problem with an additional constraint such that every vertex is required to have a specified degree. [ABSTRACT FROM AUTHOR]

We consider model based estimates for set-up time. The general setting we are interested in is the following: given a disk and a sequence of read/write requests to certain locations, we would like to know the total time of transitions (set-up time) when these requests are served in an orderly fashion. The problem becomes nontrivial when we have, as is typically the case, only the counts of requests to each location rather then the whole input, in which case we can only hope to estimate the required time. Models that estimate the set-up time have been suggested and heavily used as far back as the sixties. However, not much theory exists to enable a qualitative understanding of such models. To this end we introduce several properties through which we can study different models such as (i) super-additivity which means that the set-up time estimate decreases as the input data is refined (ii) monotonicity which means that more activity produces more set-up time, and (iii) an approximation guarantee for the estimate with respect to the worst possible time. We provide criteria for super-additivity and monotonicity to hold for popular models such as the independent reference model (IRM). The criteria show that the estimate produced by these models will be monotone for any reasonable system. We also show that the IRM based estimate functions, upto a factor of 2, as a worst case estimate to the actual set-up time. To establish our theoretical results we use the theory of finite metric spaces, and en route show a result of independent interest in that theory, which is a strengthening of a theorem of Kelly [4] about the properties of metrics that are formed by concave functions on the line. [ABSTRACT FROM AUTHOR]

The enumerate-and-expand paradigm for solving NP-hard problems has been introduced and applied to some Vertex Cover variants in a recently published preliminary paper. In this paper we improve on the runtime for Connected Vertex Cover, obtaining a bound of O*(2.7606k),The O*-notation is equivalent to the well-known Landau notation, except that polynomial factors may be suppressed. For instance, 2kk2n3=O*(2k). and use the technique in order to gain the fastest known method for counting the number of vertex covers in a graph, which takes O*(1.3803k) time. [ABSTRACT FROM AUTHOR]

Given a sequence, the problem studied in this paper is to find a set of k disjoint continuous subsequences such that the total sum of all elements in the set is maximized. This problem arises naturally in the analysis of DNA sequences. The previous best known algorithm requires Θ(n log n) time in the worst case. For a given sequence of length n, we present an almost linear-time algorithm for this problem. Our algorithm uses a disjoint-set data structure and requires O(nα(n, n)) time in the worst case, where α(n, n) is the inverse Ackermann function. [ABSTRACT FROM AUTHOR]

We define a language to be overlap-free if any two distinct strings in the language do not overlap with each other. We observe that overlap-free languages are a proper subfamily of infix-free languages and also a proper subfamily of comma-free languages. Based on these observations, we design a polynomial-time algorithm that determines overlap-freeness of a regular language. We consider two cases: A language is specified by a nondeterministic finite-state automaton and a language is described by a regular expression. Furthermore, we examine the prime overlap-free decomposition of overlap-free regular languages and show that the prime overlap-free decomposition is not unique. [ABSTRACT FROM AUTHOR]

Interval graphs play important roles in analysis of DNA chains in Benzer [1], restriction maps of DNA in Waterman and Griggs [11] and other related areas. In this paper, we study a new combinatorial optimization problem, named as the minimum clique partition problem with constrained weight, for interval graphs. For a weighted interval graph G and a bound B, partition the weighted intervals of this graph G into the smallest number of cliques, where each clique, consisting of some intervals whose intersection on a real line is not empty, has its weight not beyond B. We obtain the following results: (1) This problem is NP-hard in the strong sense, and it cannot be approximated within a ratio $\frac{3}{2}-\varepsilon$ in polynomial-time for any ε> 0; (2) We design some approximation algorithms with different constant ratios to this problem; (3) For the case where all intervals have the same weight, we also design an optimal algorithm to solve the problem in linear time. Keywords: Interval graph, cliques, approximation algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we consider an interesting variant of the well-known Steiner tree problem: Given a complete graph G = (V,E) with a cost function c:E →R+ and two subsets R and R′ satisfying $R'\subset R\subseteq V$, a selected-internal Steiner tree is a Steiner tree which contains (or spans) all the vertices in R such that each vertex in R′ cannot be a leaf. The selected-internal Steiner tree problem is to find a selected-internal Steiner tree with the minimum cost. In this paper, we show that the problem is MAX SNP-hard even when the costs of all edges in the input graph are restricted to either 1 or 2. We also present an approximation algorithm for the problem. [ABSTRACT FROM AUTHOR]

In this paper we present approximation results for the class constrained bin packing problem that has applications to Video-on-Demand Systems. In this problem we are given bins of capacity B with C compartments, and n items of Q different classes. The problem is to pack the items into the minimum number of bins, where each bin contains items of at most C different classes and has total items size at most B. We present several approximation algorithms for off-line and online versions of the problem. [ABSTRACT FROM AUTHOR]

While the complexity of min-max and min-max regret versions of most classical combinatorial optimization problems has been thoroughly investigated, there are very few studies about their approximation. For a bounded number of scenarios, we establish a general approximation scheme which can be used for min-max and min-max regret versions of some polynomial problems. Applying this scheme to shortest path and minimum spanning tree, we obtain fully polynomial-time approximation schemes with much better running times than the ones previously presented in the literature. Keywords: min-max, min-max regret, approximation, fptas, shortest path, minimum spanning tree. [ABSTRACT FROM AUTHOR]

A planar polyomino of size n is an edge-connected set of n squares on a rectangular 2-D lattice. Similarly, a d-dimensional polycube (for d ≥2) of size n is a connected set of n hypercubes on an orthogonal d-dimensional lattice, where two hypercubes are neighbors if they share a (d-1)-dimensional face. There are also two-dimensional polyominoes that lie on a triangular or hexagonal lattice. In this paper we describe a generalization of Redelmeier's algorithm for counting two-dimensional rectangular polyominoes [Re81], which counts all the above types of polyominoes. For example, our program computed the number of distinct 3-D polycubes of size 18. To the best of our knowledge, this is the first tabulation of this value. Keywords: Polycubes, lattice animals, subgraph counting. [ABSTRACT FROM AUTHOR]

In this paper we show a lower bound for the on-line version of Heilbronn's triangle problem in d dimensions. Specifically, we provide an incremental construction for positioning n points in the d-dimensional unit cube, for which every simplex defined by d + 1 of these points has volume Ω(1/n(d+1)ln (d-2)+2). [ABSTRACT FROM AUTHOR]

An axis-parallel k-dimensional box is a Cartesian product R1 ×R2 ×⋯×Rk where Ri (for 1 ≤i ≤k) is a closed interval of the form [ai, bi] on the real line. For a graph G, its boxicity$\ensuremath{\mathrm{box}}(G)$ is the minimum dimension k, such that G is representable as the intersection graph of (axis-parallel) boxes in k-dimensional space. The concept of boxicity finds applications in various areas such as ecology, operation research etc. A number of NP-hard problems are either polynomial time solvable or have much better approximation ratio on low boxicity graphs. For example, the max-clique problem is polynomial time solvable on bounded boxicity graphs and the maximum independent set problem has logn approximation ratio for boxicity 2 graphs. In most cases, the first step usually is computing a low dimensional box representation of the given graph. Deciding whether the boxicity of a graph is at most 2 itself is NP-hard. We give an efficient randomized algorithm to construct a box representation of any graph G on n vertices in 1.5 (Δ+ 2) ln n dimensions, where Δ is the maximum degree of G. We also show that $\ensuremath{\mathrm{box}}(G) \le (\Delta + 2) \ln n$ for any graph G. Our bound is tight up to a factor of ln n. The only previously known general upper bound for boxicity was given by Roberts, namely $\ensuremath{\mathrm{box}}(G) \le n/2$. Our result gives an exponentially better upper bound for bounded degree graphs. We also show that our randomized algorithm can be derandomized to get a polynomial time deterministic algorithm. Though our general upper bound is in terms of maximum degree Δ, we show that for almost all graphs on n vertices, its boxicity is upper bound by c·(dav + 1) ln n where dav is the average degree and c is a small constant. Also, we show that for any graph G, $\ensuremath{\mathrm{box}}(G) \le \sqrt{8 n d_{av} \ln n}$, which is tight up to a factor of $b \sqrt{\ln n}$ for a constant b. [ABSTRACT FROM AUTHOR]

We determine the values of the acyclic chromatic index of a class of graphs referred to as d-dimensional partial tori. These are graphs which can be expressed as the Cartesian product of d graphs each of which is an induced path or cycle. This class includes some known classes of graphs like d-dimensional meshes (hypergrids), hypercubes, tori, etc. Our estimates are exact except when the graph is a product of a path and a number of odd cycles, in which case the estimates differ by an additive factor of at most 1. Our results are also constructive and provide an optimal (or almost optimal) acyclic edge colouring in polynomial time. Keywords: Acyclic Edge Colouring, Graph, Acyclic Chromatic Index, Mesh, Hypercube, Tori. [ABSTRACT FROM AUTHOR]

Partially blind signature was first introduced by Abe and Fujisaki. Subsequently, Abe and Okamoto proposed a provably secure construction for partially blind signature schemes with a formalized definition in their work. In this paper, based on discrete logarithm problem and the Schnorr's blind signature scheme, we propose a new efficient partially blind signature scheme. Follow the construction proposed by Abe and Okamoto, we prove its security in random oracle model. The computation and communication costs are both reduced in our scheme. It will make privacy-oriented applications which based on partially blind signatures more efficient and suitable for hardware-limited environment, such as smart phones and PDAs. [ABSTRACT FROM AUTHOR]

In this paper we present several lower bounds on the approximation of the exemplar conserved interval distance problem of genomes. We first prove that the exemplar conserved interval distance problem cannot be approximated within a factor of clogn for some constant c>0 in polynomial time, unless P=NP. We then prove that it is NP-complete to decide whether the exemplar conserved interval distance between any two sets of genomes is zero or not. This result implies that the exemplar conserved interval distance problem does not admit any approximation in polynomial time, unless P=NP. In fact, this result holds even when a gene appears in each of the given genomes at most three times. Finally, we strengthen the second result under a weaker definition of approximation (which we call weak approximation). We show that the exemplar conserved interval distance problem does not admit a weak approximation within a factor of m, where m is the maximum length of the given genomes. [ABSTRACT FROM AUTHOR]

We consider the problem of reconciling gene trees with a species tree based on the widely accepted Gene Duplication model from Goodman et al. Current algorithms that solve this problem handle only binary gene trees or interpret polytomies in the gene tree as true. While in practice polytomies occur frequently, they are typically not true. Most polytomies represent unresolved evolutionary relationships. In this case a polytomy is called apparent. In this work we modify the problem of reconciling gene and species trees by interpreting polytomies to be apparent, based on a natural extension of the Gene Duplication model. We further provide polynomial time algorithms to solve this modified problem. [ABSTRACT FROM AUTHOR]

Denote by an ℓ-component a connected b-uniform hypergraph with k edges and k(b-1) - ℓ vertices. We prove that the expected number of creations of ℓ-component during a random hypergraph process tends to 1 as ℓ and b tend to ∞ with the total number of vertices n such that $\ell = o\left( \sqrt[3]{\frac{n}{b}} \right)$. Under the same conditions, we also show that the expected number of vertices that ever belong to an ℓ-component is approximately 121/3 (b-1)1/3 ℓ1/3n2/3. As an immediate consequence, it follows that with high probability the largest ℓ-component during the process is of size O( (b-1)1/3 ℓ1/3n2/3 ). Our results give insight about the size of giant components inside the phase transition of random hypergraphs. [ABSTRACT FROM AUTHOR]

In this paper, we study two interesting variants of the classical bin packing problem, called Lazy Bin Covering (LBC) and Cardinality Constrained Maximum Resource Bin Packing (CCMRBP) problems. For the offline LBC problem, we first show its NP-hardness, then prove the approximation ratio of the First-Fit-Decreasing algorithm, and finally present an APTAS. For the online LBC problem, we give competitive analysis for the algorithms of Next-Fit, Worst-Fit, First-Fit, and a modified HARMONICM algorithm. The CCMRBP problem is a generalization of the Maximum Resource Bin Packing (MRBP) problem [1]. For this problem, we prove that its offline version is no harder to approximate than the offline MRBP problem. [ABSTRACT FROM AUTHOR]

This paper gives a complete and tight mathematical analysis on the performance of the Most-Requested-First algorithm for on-demand data broadcast. The algorithm is natural and simple, yet its performance is surprisingly good in practice. We derive tight upper and lower bounds on MRF's competitiveness and thus reveal the exact competitive ratios of the algorithm under different system configurations. We prove that the competitive ratio of MRF is exactly $3 - \frac{\ell}{d}$ when the start-up delay d is a multiple of the page length ℓ; otherwise the ratio is 3. [ABSTRACT FROM AUTHOR]

We study an on-line broadcast scheduling problem in which requests have deadlines, and the objective is to maximize the weighted throughput, i.e., the weighted total length of the satisfied requests. For the case where all requested pages have the same length, we present an online deterministic algorithm named BAR and prove that it is 4.56-competitive. This improves the previous algorithm of Kim and Chwa [11] which is shown to be 5-competitive by Chan et al. [4]. In the case that pages may have different lengths, we prove a lower bound of Ω(Δ/logΔ) on the competitive ratio where Δ is the ratio of maximum to minimum page lengths. This improves upon the previous $\sqrt{\Delta}$ lower bound in [11,4] and is much closer to the current upper bound of ($\Delta+2\sqrt{\Delta}+2$) in [7]. Furthermore, for small values of Δ we give better lower bounds. [ABSTRACT FROM AUTHOR]

We study the dynamic bin packing problem introduced by Coffman, Garey and Johnson [7]. This problem is a generalization of the bin packing problem in which items may arrive and depart from the packing dynamically. The main result in this paper is a lower bound of 2.5 on the achievable competitive ratio, improving the best known 2.428 lower bound [3], and revealing that packing items of restricted form like unit fractions (i.e., of size 1/k for some integer k), which can guarantee a competitive ratio 2.4985 [3], is indeed easier. We also investigate the resource augmentation analysis on the problem where the on-line algorithm can use bins of size b (> 1) times that of the optimal off-line algorithm. An interesting result is that we prove b = 2 is both necessary and sufficient for the on-line algorithm to match the performance of the optimal off-line algorithm, i.e., achieve 1-competitiveness. Further analysis is made to give a trade-off between the bin size multiplier b and the achievable competitive ratio. [ABSTRACT FROM AUTHOR]

In a recent article, Nakhleh, Ringe and Warnow introduced perfect phylogenetic networks—a model of language evolution where languages do not evolve via clean speciation—and formulated a set of problems for their accurate reconstruction. Their new methodology assumes networks, rather than trees, as the correct model to capture the evolutionary history of natural languages. They proved the NP-hardness of the problem of testing whether a network is a perfect phylogenetic one for characters exhibiting at least three states, leaving open the case of binary characters, and gave a straightforward brute-force parameterized algorithm for the problem of running time O(3kn), where k is the number of bidirectional edges in the network and n is its size. In this paper, we first establish the NP-hardness of the binary case of the problem. Then we provide a more efficient parameterized algorithm for this case running in time O(2kn2). The presented algorithm is very simple, and utilizes some structural results and elegant operations developed in this paper that can be useful on their own in the design of heuristic algorithms for the problem. The analysis phase of the algorithm is very elegant using amortized techniques to show that the upper bound on the running time of the algorithm is much tighter than the upper bound obtained under a conservative worst-case scenario assumption. Our results bear significant impact on reconstructing evolutionary histories of languages-particularly from phonological and morphological character data, most of which exhibit at most two states (i.e., are binary), as well as on the design and analysis of parameterized algorithms. [ABSTRACT FROM AUTHOR]

Given a graph G(V, E), the identifying codes problem is to find the smallest set of vertices $D \subseteq V$ such that no two vertices in V are adjacent to the same set of vertices in D. The identifying codes problem has been applied to fault diagnosis and sensor based location detection in harsh environments. In this paper, we introduce and study a generalization of this problem, namely, the d-identifying codes problem. We propose a polynomial time approximation algorithm based on ideas from information theory and establish its approximation ratio that is very close to the best possible. Using analysis on random graphs, several fundamental properties of the optimal solution to this problem are also derived. [ABSTRACT FROM AUTHOR]

We study the complexity of some computational problems on finite black-box rings whose elements are encoded as strings of a given length and the ring operations are performed by a black-box oracle. We give a polynomial-time quantum algorithm to compute a basis representation for a given black-box ring. Using this result we obtain polynomial-time quantum algorithms for several natural computational problems over black-box rings. [ABSTRACT FROM AUTHOR]

Assume that each vertex of a graph G is assigned a constant number q of nonnegative integer weights, and that q pairs of nonnegative integers li and ui, 1 ≤i ≤q, are given. One wishes to partition G into connected components by deleting edges from G so that the total i-th weights of all vertices in each component is at least li and at most ui for each index i, 1 ≤i ≤q. The problem of finding such a "uniform" partition is NP-hard for series-parallel graphs, and is strongly NP-hard for general graphs even for q = 1. In this paper we show that the problem and many variants can be solved in pseudo-polynomial time for series-parallel graphs. Our algorithms for series-parallel graphs can be extended for partial k-trees, that is, graphs with bounded tree-width. [ABSTRACT FROM AUTHOR]

A binary sequence x1..., xn is called k-tonic if it contains at most k changes between 0 and 1, i.e., there are at most k indices such that xi ≠xi+1. A sequence $\neg x_1, \ldots, \neg x_n$ is called an inversion of x1..., xn. In this paper, we investigate the size of a negation-limited circuit, which is a Boolean circuit with a limited number of NOT gates, that sorts or inverts k-tonic input sequences. We show that if k = O(1) and t = O(loglogn), a k-tonic sequence of length n can be sorted by a circuit with t NOT gates whose size is O((n logn)/ 2ct) where c > 0 is some constant. This generalizes a similar upper bound for merging by Amano, Maruoka and Tarui [4], which corresponds to the case k = 2. We also show that a k-tonic sequence of length n can be inverted by a circuit with O(k logn) NOT gates whose size is O(kn) and depth is O(k log2n). This reduces the size of the negation-limited inverter of size O(n logn) by Beals, Nishino and Tanaka [6] when k = o(logn). If k = O(1), our inverter has size O(n) and depth O(log2n) and contains O(logn) NOT gates. For this case, the size and the number of NOT gates are optimal up to a constant factor. [ABSTRACT FROM AUTHOR]

We consider the online auction problem in which an auctioneer is selling an identical item each time when a new bidder arrives. It is known that results from online prediction can be applied and achieve a constant competitive ratio with respect to the best fixed price profit. These algorithms work on a predetermined set of price levels. We take into account the property that the rewards for the price levels are not independent and cast the problem as a more refined model of online prediction. We then use Vovk's Aggregating Strategy to derive a new algorithm. We give a general form of competitive ratio in terms of the price levels. The optimality of the Aggregating Strategy gives an evidence that our algorithm performs at least as well as the previously proposed ones. [ABSTRACT FROM AUTHOR]

We examine how to induce selfish heterogeneous users in a multicommodity network to reach an equilibrium that minimizes the social cost. In the absence of centralized coordination, we use the classical method of imposing appropriate taxes (tolls) on the edges of the network. We significantly generalize previous work [20,13,9] by allowing user demands to be elastic. In this setting the demand of a user is not fixed a priori but it is a function of the routing cost experienced, a most natural assumption in traffic and data networks. [ABSTRACT FROM AUTHOR]

The concept of tree-width and tree-decomposition of a graph plays an important role in algorithms and graph theory. Many NP-hard problems have been shown to be polynomially sovable when restricted to the class of instances with a bounded tree-width. In this paper, we establish an improved lower bound on the threshold for a random graph to have a linear treewidth, which improves the previous result by Kloks [1]. [ABSTRACT FROM AUTHOR]

A non-decreasing sequence of n integers is the degree sequence of a 1-tree (i.e., an ordinary tree) on n vertices if and only if there are least two 1's in the sequence, and the sum of the elements is 2(n-1). We generalize this result in the following ways. First, a natural generalization of this statement is a necessary condition for k-trees, and we show that it is not sufficient for any k > 1. Second, we identify non-trivial sufficient conditions for the degree sequences of 2-trees. We also show that these sufficient conditions are almost necessary using bounds on the partition function p(n) and probabilistic methods. Third, we generalize the characterization of degrees of 1-trees in an elegant and counter-intuitive way to yield integer sequences that characterize k-trees, for all k. [ABSTRACT FROM AUTHOR]

In this paper we present an algorithm for enumerating without repetitions all the non-crossing generically minimally rigid bar-and-joint frameworks (simply called non-crossing Laman frameworks) on a given generic set of n points. Our algorithm is based on the reverse search paradigm of Avis and Fukuda. It generates each output graph in O(n4) time and O(n) space, or, with a slightly different implementation, in O(n3) time and O(n2) space. In particular, we obtain that the set of all non-crossing Laman frameworks on a given point set is connected by flips which remove an edge and then restore the Laman property with the addition of a non-crossing edge. [ABSTRACT FROM AUTHOR]

We consider the problem of simplifying a triangle mesh using edge contractions, under the restriction that the resulting vertices must be a subset of the input set. That is, contraction of an edge must be made onto one of its adjacent vertices. In order to maintain a high number of contractible edges under this restriction, a small modification of the mesh around the edge to be contracted is allowed. Such a contraction is denoted a 2-step contraction. Given m "important" points or edges it is shown that a simplification hierarchy of size O(n) and depth O(log(n/m)) may be constructed in O(n) time. Further, for many edges not even 2-step contractions may be enough, and thus, the concept is generalized to k-step contractions. [ABSTRACT FROM AUTHOR]

We consider the problems of straightening polygonal trees and convexifying polygons by continuous motions such that rigid edges can rotate around vertex joints and no edge crossings are allowed. A tree can be straightened if all its edges can be aligned along a common straight line such that each edge points "away" from a designated leaf node. A polygon can be convexified if it can be reconfigured to a convex polygon. A lattice tree (resp. polygon) is a tree (resp. polygon) containing only edges from a square or cubic lattice. We first show that a 2D lattice chain or a 3D lattice tree can be straightened efficiently in O(n) moves and time, where n is the number of tree edges. We then show that a 2D lattice tree can be straightened efficiently in O(n2) moves and time. Furthermore, we prove that a 2D lattice polygon or a 3D lattice polygon with simple shadow can be convexified efficiently in O(n2) moves and time. Finally, we show that two special classes of diameter-4 trees in two dimensions can always be straightened. Keywords: Comput. geom., unfolding, straightening, convexifying. [ABSTRACT FROM AUTHOR]

We present a simple O(m + n6/ε12) time (1+ε)-approximation algorithm for the problem of cutting a convex n-gon out of a convex m-gon with line cuts of minimum total cutting length. This problem was introduced by Overmars and Welzl in the First Annual ACM Symposium on Computational Geometry in 1985. We also present a constant approximation algorithm for the generalized problem of cutting two disjoint convex polygons out of a convex polygon. [ABSTRACT FROM AUTHOR]

We consider the problem of placing a maximal number of disks in a rectangular region containing obstacles such that no two disks intersect. Let α be a fixed real in (0,1]. We are given a bounding rectangle P and a set $\cal{R}$ of possibly intersecting unit disks whose centers lie in P. The task is to pack a set $\cal{B}$ of m disjoint disks of radius α into P such that no disk in $\cal{B}$ intersects a disk in $\cal{R}$, where m is the maximum number of unit disks that can be packed. Baur and Fekete showed that the problem cannot be solved in polynomial time for α≥13/14, unless ${\cal P}={\cal NP}$. In this paper we present an algorithm for α= 2/3. [ABSTRACT FROM AUTHOR]

In this paper, we study an interesting matrix decomposition problem that seeks to decompose a "complicated" matrix into two "simpler" matrices while minimizing the sum of the horizontal complexity of the first sub-matrix and the vertical complexity of the second sub-matrix. The matrix decomposition problem is crucial for improving the "step-and-shoot" delivery efficiency in Intensity-Modulated Radiation Therapy, which aims to deliver a highly conformal radiation dose to a target tumor while sparing the surrounding normal tissues. Our algorithm is based on a non-trivial graph construction scheme, which enables us to formulate the decomposition problem as computing a minimum s-t cut in a 3-D geometric multi-pillar graph. Experiments on randomly generated intensity map matrices and on clinical data demonstrated the efficiency of our algorithm. [ABSTRACT FROM AUTHOR]

In this paper we have presented new algorithms to handle the pattern matching problem where the pattern can contain variable length gaps. Given a pattern P with variable length gaps and a text T our algorithm works in O(n + m + α log(max1<=i<=l(bi-ai))) time where n is the length of the text, m is the summation of the lengths of the component subpatterns, α is the total number of occurrences of the component subpatterns in the text and ai and bi are, respectively, the minimum and maximum number of don't cares allowed between the ith and (i+1)st component of the pattern. We also present another algorithm which, given a suffix array of the text, can report whether P occurs in T in O(m + α loglogn) time. Both the algorithms record information to report all the occurrences of P in T. Furthermore, the techniques used in our algorithms are shown to be useful in many other contexts. [ABSTRACT FROM AUTHOR]

In this paper, different parameterized versions of the longest common subsequence (LCS) problem are extensively investigated and computational lower bound results are derived based on current research progress in parameterized computation. For example, with the number of sequences as the parameter k, the problem is unlikely to be solvable in time f(k)no(k), where n is the length of each sequence and f is any recursive function. The lower bound result is asymptotically tight in consideration of the dynamic programming approach of time O(nk). Computational lower bounds for polynomial-time approximation schemes (PTAS) for the LCS problem are also derived. It is shown that the LCS problem has no PTAS of time f(1/ε)no(1/ε) for any recursive function f, unless all SNP problems are solvable in subexponential time. Compared with former results on this problem, this result has its significance. Finally a parameterized approach for the LCS problem is discussed, which is more efficient than the dynamic programming approach, especially when applied to large scale sequences. [ABSTRACT FROM AUTHOR]

We show that membership is decidable for languages defined by iterated template-guided recombination systems when the set of templates is regular and the initial language is context-free. Using this result we show that when the set of templates is regular and the initial language is context-free (respectively, regular) we can effectively construct a pushdown automaton (respectively, finite automaton) for the corresponding iterated template-guided recombination language. [ABSTRACT FROM AUTHOR]

This paper considers the quantum query complexity of ε-biased oracles that return the correct value with probability only 1/2 + ε. In particular, we show a quantum algorithm to compute N-bit OR functions with $O(\sqrt{N}/{\varepsilon})$ queries to ε-biased oracles. This improves the known upper bound of $O(\sqrt{N}/{\varepsilon}^2)$ and matches the known lower bound; we answer the conjecture raised by the paper [1] affirmatively. We also show a quantum algorithm to cope with the situation in which we have no knowledge about the value of ε. This contrasts with the corresponding classical situation, where it is almost hopeless to achieve more than a constant success probability without knowing the value of ε. [ABSTRACT FROM AUTHOR]

This paper studies the problem of finding the 1-median on a graph where vertex weights are uncertain and the uncertainty is characterized by given intervals. It is required to find a minmax regret solution, which minimizes the worst-case loss in the objective function. Averbakh and Berman had an O(mn2log n)-time algorithm for the problem on a general graph, and had an O(nlog2n)-time algorithm on a tree. In this paper, we improve these two bounds to O(mn2 + n3log n) and O(nlog n), respectively. Keywords: Location theory, minmax regret optimization, medians. [ABSTRACT FROM AUTHOR]

A module of a graph is a non-empty subset of vertices such that every non-module vertex is either connected to all or none of the module vertices. An indecomposable graph contains no non-trivial module (modules of cardinality 1 and V are trivial). We present an algorithm to compute indecomposability preserving elimination sequence, which is faster by a factor of V compared to the algorithms based on earlier published work. The algorithm is based on a constructive proof of Ille's theorem [9]. The proof uses the properties of X-critical graphs, a generalization of critical indecomposable graphs. Keywords: Module, indecomposable graph, critically indecomposable graph, elimination sequence. [ABSTRACT FROM AUTHOR]

Reversible finite automata with halting states (RFA) were first considered by Ambainis and Freivalds to facilitate the research of Kondacs-Watrous quantum finite automata. In this paper we consider some of the algebraic properties of RFA, namely the varieties these automata generate. Consequently, we obtain a characterization of the boolean closure of the classes of languages recognized by these models. [ABSTRACT FROM AUTHOR]

A circular-arc model $(C, \cal A)$ is a circle C together with a collection $\cal A$ of arcs of C. If $\cal A$ satisfies the Helly Property then $(C, \cal A)$ is a Helly circular-arc model. A (Helly) circular-arc graph is the intersection graph of a (Helly) circular-arc model. Circular-arc graphs and their subclasses have been the object of a great deal of attention, in the literature. Linear time recognition algorithm have been described both for the general class and for some of its subclasses. However, for Helly circular-arc graphs, the best recognition algorithm is that by Gavril, whose complexity is O(n3). In this article, we describe different characterizations for Helly circular-arc graphs, including a characterization by forbidden induced subgraphs for the class. The characterizations lead to a linear time recognition algorithm for recognizing graphs of this class. The algorithm also produces certificates for a negative answer, by exhibiting a forbidden subgraph of it, within this same bound. Keywords: algorithms, circular-arc graphs, forbidden subgraphs, Helly circular-arc graphs. [ABSTRACT FROM AUTHOR]