Optimum sweeps of simple polygons with two guards

A polygon P admits a sweep if two mobile guards can detect an unpredictable, moving target inside P  , no matter how fast the target moves. Two guards move on the polygon boundary and are required to always be mutually visible. The objective of this study is to find an optimum sweep such that the sum of the distances travelled by the two guards in the sweep is minimized. We present an O(n²)$O(n^2)$ time and O(n)$O(n)$ space algorithm for optimizing this metric, where n   is the number of vertices of the given polygon. Our result is obtained by reducing this problem to finding a shortest path between two nodes in a graph of size O(n)$O(n)$.     

Finding the nucleolus of any n-person cooperative game by a single linear program

In this paper we show a new method for calculating the nucleolus by solving a unique minimization linear program with O(4ⁿ)$O(4^n)$ constraints whose coefficients belong to {−1,0,1}$\{-1,0,1\}$. We discuss the need of having all these constraints and empirically prove that they can be reduced to O(_kmax2ⁿ)$O(k_{\mathit{max}}{2}^n)$, where k_max is a positive integer comparable with the number of players. A computational experience shows the applicability of our method over (pseudo)random transferable utility cooperative games with up to 18 players.     

On approximating metric 1-median in sublinear time

This paper focuses on approximating the metric 1-median problem with sublinear number of queries and time complexity. We first show a simper proof of the currently best 4-approximation algorithm, and then propose a recursive algorithm. For any integer h?2$h?2$, the algorithm finds a 2h  -approximation solution with O(n^1+1/h)$O(n^{1+1/h})$ queries and time complexity.     

Computing the pathwidth of directed graphs with small vertex cover

We give an algorithm that computes the pathwidth of a given directed graph D   in 3^τ(D)n^O(1)$3^{\tau (D)}{n}^{O(1)}$ time where n is the number of vertices of D   and τ(D)$\tau (D)$ is the number of vertices of a minimum vertex cover of the underlying undirected graph of D. This result extends that of [5] for undirected graphs to directed graphs. Moreover, our algorithm is based on a standard dynamic programming with a simple tree-pruning trick, which is extremely simple and easy to implement. An additional advantage of our algorithm is that a minimum vertex cover appears in the analysis but not in the algorithm itself, in contrast to the algorithm of [5] which needs to compute a minimum vertex cover.     

Flip-pushdown automata with k pushdown reversals and E0L systems are incomparable

We prove that any propagating E0L system cannot generate the language {w#w|w∈{0,1}^?}$\{w\mathrm{\#}w|w\in {\{0,1\}}^{?}\}$. This result, together with some known ones, enables us to conclude that the flip-pushdown automata with k pushdown reversals, i.e., the pushdown automata with the ability to flip the pushdown, and E0L systems are incomparable. This result solves an open problem stated by Holzer and Kutrib in 2003.     

Some properties of the induced continuous ordered weighted geometric operators in group decision making

In Computers and Industrial Engineering 56 (2009) 1545–1552, an induced continuous ordered weighted geometric (ICOWG) operator is presented to deal with group decision making (GDM) problems with interval multiplicative preference relations. But, we still do not know whether the ICOWG operator can improve the consensus among a group of decision makers. The aim of this paper is to study some desired properties of the ICOWG operator in GDM problems. Firstly, the concept of Compatibility Degree and Compatibility Index (CI) is defined. We then present the Compatibility Index induced COWG (CI-ICOWG) operator to aggregate interval multiplicative preference relations, which induces the order of argument values based on the Compatibility Index of decision makers (DMs). The main novelty of the CI-ICOWG operator is that it aggregates individual preference relation in such a way that more importance is placed on the most compatibility one. Thus, the CI-ICOWG operator can guarantee that the Compatibility Degree is at least as good as the arithmetic mean of all the individual Compatibility Degrees. Additionally, if the leading decision maker’s interval multiplicative preference relation P   and each of interval multiplicative preference relations R⁽¹⁾,R⁽²⁾,…,R^(m)$R^{(1)}\text{,}{R}^{(2)}\text{,}\dots \text{,}{R}^{(m)}$ are of acceptable compatibility, then P   and the collective judgement matrix (CJM) of R⁽¹⁾,R⁽²⁾,…,R^(m)$R^{(1)}\text{,}{R}^{(2)}\text{,}\dots \text{,}{R}^{(m)}$ are of acceptable compatibility. Finally, an illustrative numerical example is used to verify the developed approaches.     

An exact exponential time algorithm for counting bipartite cliques

We present a simple exact algorithm for counting bicliques of given size in a bipartite graph on n   vertices. We achieve running time of O(1.2491ⁿ)$O({1.2491}^n)$, improving upon known exact algorithms for finding and counting bipartite cliques.     

On the partition dimension of a class of circulant graphs

For a vertex v   of a connected graph G(V,E)$G(V,E)$ and a subset S of V, the distance between a vertex v and S   is defined by d(v,S)=min{d(v,x):x∈S}$d(v,S)=\min \{d(v,x):x\in S\}$. For an ordered k  -partition π={_S1,_S2…_Sk}$\pi =\{S_1,S_2\dots S_k\}$ of V, the partition representation of v with respect to π is the k  -vector r(v|π)=(d(v,_S1),d(v,_S2)…d(v,_Sk))$r(v|\pi )=(d(v,S_1),d(v,S_2)\dots d(v,S_k))$. The k-partition π is a resolving partition if the k  -vectors r(v|π)$r(v|\pi )$, v∈V(G)$v\in V(G)$ are distinct. The minimum k for which there is a resolving k-partition of V is the partition dimension of G. Salman et al. [1] in their paper which appeared in Acta Mathematica Sinica, English Series   proved that partition dimension of a class of circulant graph G(n,±{1,2})$G(n,\pm \{1,2\})$, for all even n?6$n?6$ is four. In this paper we prove that it is three.     

On a compact encoding of the swap automaton

Given a string P of length m over an alphabet Σ of size σ, a swapped version of P is a string derived from P   by a series of local swaps, i.e., swaps of adjacent symbols, such that each symbol can participate in at most one swap. We present a theoretical analysis of the nondeterministic finite automaton for the language _?P′∈ΠPΣ^?P^′${?}_{P^{\prime }\in {\Pi }_P}{\Sigma }^{?}{P}^{\prime }$ (swap automaton, for short), where _ΠP${\Pi }_P$ is the set of swapped versions of P  . Our study is based on the bit-parallel simulation of the same automaton due to Fredriksson, and reveals an interesting combinatorial property that links the automaton to the one for the language Σ^?P${\Sigma }^{?}P$. By exploiting this property and the method presented by Cantone et al. (2012), we obtain a bit-parallel encoding of the swap automaton which takes O(σ²⌈k/w⌉)$O({\sigma }^2\lceil k/w\rceil )$ space and allows one to simulate the automaton on a string of length n   in time O(n⌈k/w⌉)$O(n\lceil k/w\rceil )$, where ⌈m/σ⌉?k?m$\lceil m/\sigma \rceil ?k?m$ is the size of a specific factorization of P defined by Cantone et al. (2012) and w is the word size in bits.     

Fast algorithms for some dominating induced matching problems

We describe O(n)$O(n)$ time algorithms for finding the minimum weighted dominating induced matching of chordal, dually chordal, biconvex, and claw-free graphs. For the first three classes, we prove tight O(n)$O(n)$ bounds on the maximum number of edges that a graph having a dominating induced matching may contain. By applying these bounds, and employing existing O(n+m)$O(n+m)$ time algorithms we show that they can be reduced to O(n)$O(n)$ time. For claw-free graphs, we describe a variation of the existing algorithm for solving the unweighted version of the problem, which decreases its complexity from O(n²)$O(n^2)$ to O(n)$O(n)$, while additionally solving the weighted version. The same algorithm can be easily modified to count the number of DIM's of the given graph.