Algorithms for Maximum Independent Set in Convex Bipartite Graphs

A bipartite graph G=(V,W,E) is convex if there exists an ordering of the vertices of W such that, for each v∈V, the neighbors of v are consecutive in W. We describe both a sequential and a BSP/CGM algorithm to find a maximum independent set in a convex bipartite graph. The sequential algorithm improves over the running time of the previously known algorithm and the BSP/CGM algorithm is a parallel version of the sequential one. The complexity of the algorithms does not depend on |W|. This work was supported by FAPESP (Proc. 98/06327-0). The first author was also supported by FAPESP (Proc. 96/04505–2), and CNPq/MCT/FINEP (PRONEX project 107/97).     

On very true operators on pocrims

Hájek introduced the logic enriching the logic BL by a unary connective vt which is a formalization of Zadeh’s fuzzy truth value “very true”. algebras, i.e., BL-algebras with unary operations, called vt-operators, which are among others subdiagonal, are an algebraic counterpart of Partially ordered commutative integral residuated monoids (pocrims) are common generalizations of both BL-algebras and Heyting algebras. The aim of our paper is to introduce and study algebraic properties of pocrims endowed by “very-true” and “very-false”-like operators. Research is supported by the Research and Development Council of Czech Government via project MSN 6198959214.     

Distributed verification of minimum spanning trees

The problem of verifying a Minimum Spanning Tree (MST) was introduced by Tarjan in a sequential setting. Given a graph and a tree that spans it, the algorithm is required to check whether this tree is an MST. This paper investigates the problem in the distributed setting, where the input is given in a distributed manner, i.e., every node “knows” which of its own emanating edges belong to the tree. Informally, the distributed MST verification problem is the following. Label the vertices of the graph in such a way that for every node, given (its own state and label and) the labels of its neighbors only, the node can detect whether these edges are indeed its MST edges. In this paper, we present such a verification scheme with a maximum label size of O(log n log W), where n is the number of nodes and W is the largest weight of an edge. We also give a matching lower bound of Ω(log n log W) (as long as W > (log n)^1+ε for some fixed ε > 0). Both our bounds improve previously known bounds for the problem. For the related problem of tree sensitivity also presented by Tarjan, our method yields rather efficient schemes for both the distributed and the sequential settings. A preliminary version of this work was presented in ACM PODC 2006. A. Korman was supported in part at the Technion by an Aly Kaufman fellowship. S. Kutten was supported in part by a grant from the Israeli Ministry for Science and Technology.     

Sequential operators in computability logic

Computability logic (CL) is a semantical platform and research program for redeveloping logic as a formal theory of computability, as opposed to the formal theory of truth which it has more traditionally been. Formulas in CL stand for (interactive) computational problems, understood as games between a machine and its environment; logical operators represent operations on such entities; and “truth” is understood as existence of an effective solution, i.e., of an algorithmic winning strategy.The formalism of CL is open-ended, and may undergo series of extensions as the study of the subject advances. The main groups of operators on which CL has been focused so far are the parallel, choice, branching, and blind operators, with the logical behaviors of the first three groups resembling those of the multiplicatives, additives and exponentials of linear logic, respectively. The present paper introduces a new important group of operators, called sequential. The latter come in the form of sequential conjunction and disjunction, sequential quantifiers, and sequential recurrences (“exponentials”). As the name may suggest, the algorithmic intuitions associated with this group are those of sequential computations, as opposed to the intuitions of parallel computations associated with the parallel group of operations. Specifically, while playing a parallel combination of games means playing all components of the combination simultaneously, playing a sequential combination means playing the components in a sequential fashion, one after one.The main technical result of the present paper is a sound and complete axiomatization of the propositional fragment of computability logic whose vocabulary, together with negation, includes all three — parallel, choice and sequential — sorts of conjunction and disjunction. An extension of this result to the first-order level is also outlined.     

The cyclic Douglas–Rachford algorithm with r-sets-Douglas–Rachford operators

The Douglas–Rachford (DR) algorithm is an iterative procedure that uses sequential reflections onto convex sets and which has become popular for convex feasibility problems. In this paper we propose a structural generalization that allows to use r-sets-DR operators in a cyclic fashion. We prove convergence and present numerical illustrations of the potential advantage of such operators with r>2 over the classical 2-sets-DR operators in a cyclic algorithm.     

Power load forecasts based on hybrid PSO with Gaussian and adaptive mutation and Wv-SVM

This paper presents a new load forecasting model based on hybrid particle swarm optimization with Gaussian and adaptive mutation (HAGPSO) and wavelet v-support vector machine (Wv-SVM). Firstly, it is proved that mother wavelet function can build a set of complete base through horizontal floating and form the wavelet kernel function. And then, Wv-SVM with wavelet kernel function is proposed in this paper. Secondly, aiming to the disadvantage of standard PSO, HAGPSO is proposed to seek the optimal parameter of Wv-SVM. Finally, the load forecasting model based on HAGPSO and Wv-SVM is proposed in this paper. The results of application in load forecasts show the proposed model is effective and feasible.     

Short Cycles Make W-hard Problems Hard: FPT Algorithms for W-hard Problems in Graphs with no Short Cycles

We show that several problems that are hard for various parameterized complexity classes on general graphs, become fixed parameter tractable on graphs with no small cycles. More specifically, we give fixed parameter tractable algorithms for Dominating Set, t -Vertex Cover (where we need to cover at least t edges) and several of their variants on graphs with girth at least five. These problems are known to be W[i]-hard for some i≥1 in general graphs. We also show that the Dominating Set problem is W[2]-hard for bipartite graphs and hence for triangle free graphs. In the case of Independent Set and several of its variants, we show these problems to be fixed parameter tractable even in triangle free graphs. In contrast, we show that the Dense Subgraph problem where one is interested in finding an induced subgraph on k vertices having at least l edges, parameterized by k, is W[1]-hard even on graphs with girth at least six. Finally, we give an O(log p) ratio approximation algorithm for the Dominating Set problem for graphs with girth at least 5, where p is the size of an optimum dominating set of the graph. This improves the previous O(log n) factor approximation algorithm for the problem, where n is the number of vertices of the input graph. A preliminary version of this paper appeared in the Proceedings of 10th Scandinavian Workshop on Algorithm Theory (SWAT), Lecture Notes in Computer Science, vol. 4059, pp. 304–315, 2006.     

(I,A)-蕴涵及其基本性质

模糊蕴涵在模糊逻辑和近似推理领域中发挥着十分重要的作用，模糊蕴涵的构造是相关领域中的重要研究课题。基于模糊蕴涵[I]和聚合算子[A]构造出[(I,A)]-算子，研究[(I,A)]-算子成为模糊蕴涵的条件，其次研究[(I,A)]-蕴涵包括分配性和输入性在内的一些基本性质。     

Action Refinement Applied to Late Decisions

In modular approaches to specify concurrent systems a system is built up from components using various operators as e.g. the sequential, the parallel, or the choice (+) operator. Usually the choice between two components, i.e. P₁ + P₂, is taken in favor of that component that is first to start an action. We follow here the alternative view that a choice is taken in favor of that component that is the first to terminate an action (end-based choice). This alternative has various applications and interesting implications. In particular the different points of view lead to different action refinement operators. The contribution of this paper is to present here an action refinement operator for the end-based view in a suitable true concurrency setting and to establish two equivalences that are the coarsest congruences for this refinement operator with respect to trace (respectively bisimulation) equivalence. Received July 2003 Revised November 2005 Accepted December 2005 by E. Astesiano     

带间隔约束的Top-k对比序列模式挖掘

对比序列模式能够表达序列数据集合间的差异,在商品推荐、用户行为分析和电力供应预测等领域有广泛的应用.已有的对比序列模式挖掘算法需要用户设定正例支持度阈值和负例支持度阈值.在不具备足够先验知识的情况下,用户难以设定恰当的支持度阈值,从而可能错失一些对比显著的模式.为此,提出了带间隔约束的top-k对比序列模式挖掘算法kDSP-Miner(top-k distinguishing sequential patterns with gap constraint miner).kDSP-Miner中用户只需设置期望发现的对比最显著的模式个数,从而避免了直接设置对比支持度阈值.相应地,挖掘算法更容易使用,并且结果更易于解释.同时,为了提高算法执行效率,设计了若干剪枝策略和启发策略.进一步设计了kDSP-Miner的多线程版本,以提高其对高维序列元素情况的处理能力.通过在真实世界数据集上的详实实验,验证了算法的有效性和执行效率.     

TSP: Mining top-k closed sequential patterns

Sequential pattern mining has been studied extensively in the data mining community. Most previous studies require the specification of a min_support threshold for mining a complete set of sequential patterns satisfying the threshold. However, in practice, it is difficult for users to provide an appropriate min_support threshold. To overcome this difficulty, we propose an alternative mining task: mining top-k frequent closed sequential patterns of length no less than min_, where k is the desired number of closed sequential patterns to be mined and min_ is the minimal length of each pattern. We mine the set of closed patterns because it is a compact representation of the complete set of frequent patterns. An efficient algorithm, called TSP, is developed for mining such patterns without min_support. Starting at (absolute) min_support=1, the algorithm makes use of the length constraint and the properties of top-k closed sequential patterns to perform dynamic support raising and projected database pruning. Our extensive performance study shows that TSP has high performance. In most cases, it outperforms the efficient closed sequential pattern-mining algorithm, CloSpan, even when the latter is running with the best tuned min_support threshold. Thus, we conclude that, for sequential pattern mining, mining top-k frequent closed sequential patterns without min_support is more preferable than the traditional min_support-based mining.     

Fast string correction with Levenshtein automata

The Levenshtein distance between two words is the minimal number of insertions, deletions or substitutions that are needed to transform one word into the other. Levenshtein automata of degree n for a word W are defined as finite state automata that recognize the set of all words V where the Levenshtein distance between V and W does not exceed n. We show how to compute, for any fixed bound n and any input word W, a deterministic Levenshtein automaton of degree n for W in time linear to the length of W. Given an electronic dictionary that is implemented in the form of a trie or a finite state automaton, the Levenshtein automaton for W can be used to control search in the lexicon in such a way that exactly the lexical words V are generated where the Levenshtein distance between V and W does not exceed the given bound. This leads to a very fast method for correcting corrupted input words of unrestricted text using large electronic dictionaries. We then introduce a second method that avoids the explicit computation of Levenshtein automata and leads to even improved efficiency. Evaluation results are given that also address variants of both methods that are based on modified Levenshtein distances where further primitive edit operations (transpositions, merges and splits) are used. Received: 13 February 2002 / Accepted: 13 March 2002     

命题线性时序逻辑的对偶模型问题的复杂性

定义了一个命题线性时序逻辑的对偶模型的概念.一个公式f的对偶模型是指f的满足以下条件的两个模型(即状态的w序列):在每个位置上这两个模型对原子命题的赋值都是对偶的.然后,对于确定一个公式f是否有对偶模型的判定问题(记为DM)和在一个Kripke-结构中确定是否存在从两个给定状态出发的对偶模型满足给定公式f的判定问题(记为KDM)的复杂性进行了研究.证明了以下结果:对于只含有F("Future")算子的命题线性时序逻辑,DM和KDM都是NP完全的;而对于以下命题线性时序逻辑,DM和KDM都是PSPACE完全的:含有F,X ("Next")算子的逻辑、含有U("Until")算子的逻辑、含有U,S,X算子的逻辑以及由Wolper给出的含有正规语言算子的逻辑(一般称为扩展时序逻辑,简称ETL).     

Process controllability analysis using linear programming

Controllability analysis is concerned with determining the limitations on achievable dynamic performance. This paper proposes the use of linear programming to determine the best linear controller and corresponding dynamic performance for problems of the form: . That is, a controller, K, and a reference operating point, u₀, are selected to minimise a specified objective, J, while ensuring feasibility for all disturbances, w, within a specified set, W. When K is a linear time invariant (LTI) controller and the objective function J and the constraints c can be expressed as linear functions then the above problem can be solved by linear programming. This formulation encompasses a wide range of problems ranging from minimising the maximum deviation in the regulated outputs subject to disturbances of magnitude less than one (the l₁ optimal control problem) to optimising the expected value of a linear economic objective (the Optimal Linear Dynamic Economics (OLDE) problem). The relationship of this work to other approaches to controllability analysis is discussed. A highly flexible framework for addressing typical process performance requirements through appropriate selection of J, c and W is presented. The relative merits of alternative approaches for defining the achievable closed loop transfer functions based on the -parameterisation are carefully discussed. The feasibility of the proposed approach is demonstrated on an industrial reactor example. The needs for further work are discussed.     

Some restrictions onW-grammars

The effect of some restrictions onW-grammars (the fonnalization of the syntax ofalgol 68) are explored. Two incomparable families examined at length areW _rb (languages generated by normal regular-basedW-grammars) andW _s (languages generated by simpleW-grammars). Both properly contain the context-free languages and are properly contained in the family of quasi-realtime languages. In addition,W _rb is closed under nested iterated substitution (but is not anAFL) and is properly contained in the family of index languages.The research represented in this paper was supported in part by the National Science Foundation under Grant GJ-803.     

Informative labeling schemes for graphs

This paper introduces the notion of informative labeling schemes for arbitrary graphs. Let f(W) be a function on subsets of vertices W. An f labeling scheme labels the vertices of a weighted graph G in such a way that f(W) can be inferred (or at least approximated) efficiently for any vertex subset W of G by merely inspecting the labels of the vertices of W, without having to use any additional information sources.A number of results illustrating this notion are presented in the paper. We begin by developing f labeling schemes for three functions f over the class of n-vertex trees. The first function, SepLevel, gives the separation level of any two vertices in the tree, namely, the depth of their least common ancestor. The second, LCA, provides the least common ancestor of any two vertices. The third, Center, yields the center of any three given vertices v₁,v₂,v₃ in the tree, namely, the unique vertex z connected to them by three edge-disjoint paths. All of these three labeling schemes use O-bit labels, which is shown to be asymptotically optimal.Our main results concern the function Steiner(W), defined for weighted graphs. For any vertex subset W in the weighted graph G, Steiner(W) represents the weight of the Steiner tree spanning the vertices of W in G. Considering the class of n-vertex trees with M-bit edge weights, it is shown that for this class there exists a Steiner labeling scheme using O((M+logn)logn) bit labels, which is asymptotically optimal. It is then shown that for the class of arbitrary n-vertex graphs with M-bit edge weights, there exists an approximate-Steiner labeling scheme, providing an estimate (up to a factor of O(logn)) for the Steiner weight Steiner(W) of a given set of vertices W, using O bit labels.     

S‐H OWA Operators with Moment Measure

Step‐like or Hurwicz‐like ordered weighted averaging (OWA) (S‐H OWA) operators connect two fundamental OWA operators, step OWA operators and Hurwicz OWA operators. S‐H OWA operators also generalize them and some other well‐know OWA operators such as median and centered OWA operators. Generally, there are two types of determination methods for S‐H OWA operators: One is from the motivation of some existed mathematical results; the other is by a set of “nonstrict” definitions and often via some intermediate elements. For the second type, in this study we define two sets of strict definitions for Hurwitz/step degree, which are more effective and necessary for theoretical studies and practical usages. Both sets of definitions are useful in different situations. In addition, they are based on the same concept moment of OWA operators proposed in this study, and therefore they become identical in limit forms. However, the Hurwicz/step degree (HD/SD) puts more concerns on its numerical measure and physical meaning, whereas the relative Hurwicz/step degree (rHD/rSD), still being accurate numerically, sometimes is more reasonable intuitively and has larger potential in further studies and practical applications.     

Structure and Recognition of Graphs with No 6-wheel Subdivision

The subgraph homeomorphism problem has been shown by Robertson and Seymour to be polynomial-time solvable for any fixed pattern graph H. The result, however, is not practical, involving constants that are worse than exponential in |H|. Practical algorithms have only been developed for a few specific pattern graphs, the most recent of these being the wheels with four and five spokes. This paper looks at the subgraph homeomorphism problem where the pattern graph is a wheel with six spokes. The main result is a theorem characterizing graphs that do not contain subdivisions of W ₆. We give an efficient algorithm for solving the subgraph homeomorphism problem for W ₆. We also give a strengthening of the previous W ₅ result.     

Lightweight Data Indexing and Compression in External Memory

In this paper we describe algorithms for computing the Burrows-Wheeler Transform (bwt) and for building (compressed) indexes in external memory. The innovative feature of our algorithms is that they are lightweight in the sense that, for an input of size n, they use only n bits of working space on disk while all previous approaches use Θ(nlog n) bits. This is achieved by building the bwt directly without passing through the construction of the Suffix Array/Tree data structure. Moreover, our algorithms access disk data only via sequential scans, thus they take full advantage of modern disk features that make sequential disk accesses much faster than random accesses. We also present a scan-based algorithm for inverting the bwt that uses Θ(n) bits of working space, and a lightweight internal-memory algorithm for computing the bwt which is the fastest in the literature when the available working space is o(n) bits. Finally, we prove lower bounds on the complexity of computing and inverting the bwt via sequential scans in terms of the classic product: internal-memory space × number of passes over the disk data, showing that our algorithms are within an O(log n) factor of the optimal.