On convergence properties of the stress ratio algorithm for inhomogeneous elastic structures

Stress-ratio-type structural optimization algorithm for inhomogeneous elastic structures (trusses) is considered. The structures are loaded by a single system of static loads. It is demonstrated that the algorithm, known as a heuristic one, may be considered in some particular case as actually based on optimality conditions. The purpose of the paper is to reveal the case and conditions when the algorithm is monotonous, prove the monotonicity, and demonstrate convergence of the algorithm.     

New efficient algorithms for the LCS and constrained LCS problems

In this paper, we study the classic and well-studied longest common subsequence (LCS) problem and a recent variant of it, namely the constrained LCS (CLCS) problem. In the CLCS problem, the computed LCS must also be a supersequence of a third given string. In this paper, we first present an efficient algorithm for the traditional LCS problem that runs in O(Rloglogn+n) time, where R is the total number of ordered pairs of positions at which the two strings match and n is the length of the two given strings. Then, using this algorithm, we devise an algorithm for the CLCS problem having time complexity O(pRloglogn+n) in the worst case, where p is the length of the third string.     

A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements

We introduce a simple, linear time algorithm for recognizing trivially perfect (TP) graphs. It improves upon the algorithm of Yan et al. [J.-H. Yan, J.-J. Chen, G.J. Chang, Quasi-threshold graphs, Discrete Appl. Math. 69 (3) (1996) 247–255] in that it is certifying, producing a P₄ or a C₄ when the graph is not TP. In addition, our algorithm can be easily modified to recognize the complement of TP graphs (co-TP) in linear time as well. It is based on lexicographic BFS, and in particular the technique of partition refinement, which has been used in the recognition of many other graph classes [D.G. Corneil, Lexicographic breadth first search—a survey, in: WG 2004, in: Lecture Notes in Comput. Sci., vol. 3353, Springer, 2004, pp. 1–19].     

Efficient algorithms for clique problems

The k-clique problem is a cornerstone of NP-completeness and parametrized complexity. When k is a fixed constant, the asymptotically fastest known algorithm for finding a k-clique in an n-node graph runs in O(n0.792k) time (given by Nešet?il and Poljak). However, this algorithm is infamously inapplicable, as it relies on Coppersmith and Winograd's fast matrix multiplication.We present good combinatorial algorithms for solving k-clique problems. These algorithms do not require large constants in their runtime, they can be readily implemented in any reasonable random access model, and are very space-efficient compared to their algebraic counterparts. Our results are the following:

•

We give an algorithm for k-clique that runs in O(nk/(εlogn)^k−1) time and O(nε) space, for all ε>0, on graphs with n nodes. This is the first algorithm to take o(nk) time and O(nc) space for c independent of k.

•

Let k be even. Define a k-semiclique to be a k-node graph G that can be divided into two disjoint subgraphs U={u₁,…,uk/2} and V={v₁,…,vk/2} such that U and V are cliques, and for all i?j, the graph G contains the edge {ui,vj}. We give an time algorithm for determining if a graph has a k-semiclique. This yields an approximation algorithm for k-clique, in the following sense: if a given graph contains a k-clique, then our algorithm returns a subgraph with at least 3/4 of the edges in a k-clique.

     

An efficient algorithm for Horn description

We give a new algorithm for computing a prepositional Horn CNF formula given the set of its models. Its running time is O(|R|n(|R|+n)), where |R| is the number of models and n that of variables, and the computed CNF contains at most |R|n clauses. This algorithm also uses the well-known closure property of Horn relations in a new manner.     

A direct algorithm for restricted rotation distance

In this paper we present a concise O(n) implementation of Cleary's algorithm for generating a sequence of restricted rotations between any two binary trees. The algorithm is described directly in terms of the binary trees, without using any intermediate representation.     

Faster index for property matching

In this paper, we revisit the Property Matching problem studied by Amir et al. [Property Matching and Weighted Matching, CPM 2006] and present a better indexing scheme for the problem. In particular, the data structure by Amir et al., namely PST, requires O(nlog|Σ|+nloglogn) construction time and O(mlog|Σ|+K) query time, where n and m are the length of, respectively, the text and the pattern, Σ is the alphabet and K is the output size. On the other hand, the construction time of our data structure, namely IDS_PIP, is dominated by the suffix tree construction time and hence is O(n) time for alphabets that are natural numbers from 1 to a polynomial in n and O(nlogσ) time otherwise, where σ=min(n,|Σ|). The query time is same as that of PST. Also, IDS_PIP has the advantage that it can be built on either a suffix tree or a suffix array and additionally, it retains the capability of answering normal pattern matching queries.     

Bounds on Mincut for Cayley Graphs over Abelian Groups

In this paper we find upper bounds for the mincut value of Cayley graphs over abelian groups. These results provide a significant improvement of those in Annextein and Baumslag (Math. Syst. Theory 26(3):271–291, [1993]). Partially supported by the Lynn and William Frankel Center for Computer Sciences.     

On mimicking networks representing minimum terminal cuts

Given a capacitated undirected graph G=(V,E)$G=(V,E)$ with a set of terminals K⊂V$K\subset V$, a mimicking network   is a smaller graph H=(_VH,_EH)$H=(V_H,E_H)$ which contains the set of terminals K   and for every bipartition [U,K−U]$[U,K-U]$ of the terminals, the cost of the minimum cut separating U   from K−U$K-U$ in G is exactly equal to the cost of the minimum cut separating U   from K−U$K-U$ in H.     

On finding cycle bases and fundamental cycle bases with a shortest maximal cycle

An undirected biconnected graph G with nonnegative integer lengths on the edges is given. The problem we consider is that of finding a cycle basis B of G such that the length of the longest cycle included in B is the smallest among all cycle bases of G. We first observe that Horton's algorithm [SIAM J. Comput. 16 (2) (1987) 358-366] provides a fast solution of the problem that extends the one given by Chickering et al. [Inform. Process. Lett. 54 (1995) 55-58] for uniform graphs. On the other hand we show that, if the basis is required to be fundamental, then the problem is NP-hard and cannot be approximated within 2−?, ∀?>0, even with uniform lengths, unless P=NP. This problem remains NP-hard even restricted to the class of complete graphs; in this case it cannot be approximated within 13/11−?, ∀?>0, unless P=NP; it is instead approximable within 2 in general, and within 3/2 if the triangle inequality holds.     

On the longest increasing subsequence of a circular list

The longest increasing circular subsequence (LICS) of a list is considered. A Monte Carlo algorithm to compute it is given which has worst case execution time O(n3/2logn) and storage requirement O(n). It is proved that the expected length μ(n) of the LICS satisfies . Numerical experiments with the algorithm suggest that .     

An FPT algorithm in polynomial space for the Directed Steiner Tree problem with Limited number of Diffusing nodes

Given a directed graph with n nodes, a root r, a set X of k nodes called terminals and non-negative weights ω   over the arcs, the Directed Steiner Tree problem (DST) asks for a directed tree T^?$T^{?}$ of minimum cost ω(T^?)$\omega (T^{?})$ rooted at r and spanning X.     

On packing shortest cycles in graphs

We study the problems to find a maximum packing of shortest edge-disjoint cycles in a graph of given girth g (g-ESCP) and its vertex-disjoint analogue g-VSCP. In the case g=3, Caprara and Rizzi (2001) have shown that g-ESCP can be solved in polynomial time for graphs with maximum degree 4, but is APX-hard for graphs with maximum degree 5, while g-VSCP can be solved in polynomial time for graphs with maximum degree 3, but is APX-hard for graphs with maximum degree 4. For g∈{4,5}, we show that both problems allow polynomial time algorithms for instances with maximum degree 3, but are APX-hard for instances with maximum degree 4. For each g?6, both problems are APX-hard already for graphs with maximum degree 3.     

The cycle roommates problem: a hard case of kidney exchange

Recently, a number of interesting algorithmic problems have arisen from the emergence, in a number of countries, of kidney exchange schemes, whereby live donors are matched with recipients according to compatibility and other considerations. One such problem can be modeled by a variant of the well-known stable roommates problem in which blocking cycles, as well as the normal blocking pairs, are significant. We show here that this variant of the stable roommates problem is NP-complete, thus solving an open question posed by Cechlárová and Lacko.     

Linear time algorithms for counting the number of minimal vertex covers with minimum/maximum size in an interval graph

This paper presents efficient algorithms for an interval graph. These are (1) an algorithm for counting the number of minimum vertex covers, and (2) an algorithm for counting the number of maximum minimal vertex covers.     

Efficient algorithms for the longest common subsequence in k-length substrings

Finding the longest common subsequence in k-length substrings (LCSk) is a recently proposed problem motivated by computational biology. This is a generalization of the well-known LCS problem in which matching symbols from two sequences A and B are replaced with matching non-overlapping substrings of length k from A and B. We propose several algorithms for LCSk, being non-trivial incarnations of the major concepts known from LCS research (dynamic programming, sparse dynamic programming, tabulation). Our algorithms make use of a linear-time and linear-space preprocessing finding the occurrences of all the substrings of length k from one sequence in the other sequence.