Search

This paper introduces a framework for building probabilistic models with subsequential failure transducers. We first show how various types of subsequential transducers commonly used in natural language processing are represented by conditional probabilistic subsequential transducers and probabilistic subsequential failure transducers. Afterwards, we introduce efficient algorithms for composition of conditional probabilistic subsequential transducers with probabilistic subsequential failure transducers and canonization (weight-pushing) of probabilistic subsequential failure transducers. Those algorithms are applicable to many tasks for representing probabilistic models. One such task is the construction of the H C L G weighted transducer used in speech recognition which we describe in detail. At the end, a comparison between the presented H C L G failure weighted transducer and the standard H C L G weighted transducer along with empirical results for HMM-based speech recognition decoding reveal the competitiveness of the presented constructions. [ABSTRACT FROM AUTHOR]

For an m -edge connected simple graph G , finding a spanning tree of G with the maximum number of leaves is MAXSNP-complete. The problem remains NP-complete even if G is planar and the maximal degree of G is at most four. Lu and Ravi gave the first known polynomial-time approximation algorithms with approximation factors 5 and 3. Later, they obtained a 3 -approximation algorithm that runs in near-linear time. The best known result is Solis-Oba, Bonsma, and Lowski's O (m) -time 2 -approximation algorithm. We show an alternative simple O (m) -time 2 -approximation algorithm whose analysis is simpler. This paper is dedicated to the cherished memory of our dear friend, Professor Takao Nishizeki. [ABSTRACT FROM AUTHOR]

This paper uses multi-sensor data fusion technology to design and develop a multi-sensor based basketball robot's target recognition and positioning system in an unknown environment. We establish the movement model of the basketball robot, and combine the hardware configuration of the basketball robot, analyse the methods of speed control, position control, and direction control, propose a fuzzy obstacle avoidance strategy in the basketball robot movement process, and simulate the obstacle avoidance strategy. The simulation results show that the proposed fuzzy obstacle avoidance strategy is effective. Carry out the experiment of basketball robot target calibration, build the basketball robot monitoring system, and realize data transmission and real-time image processing. Experiments show that the basketball robot can achieve target recognition and positioning tasks in an unknown environment (obstacle comparison rules). It proves the effectiveness and robustness of the proposed following algorithm. It illustrates the effectiveness of the system designed in this paper. [ABSTRACT FROM AUTHOR]

For an optimization problem known to be NP-Hard, the dichotomy study investigates the reduction instances to determine the line separating polynomial-time solvable vs NP-Hard instances (easy vs hard instances). In this paper, we investigate the well-studied Hamiltonian cycle problem (HCYCLE), and present an interesting dichotomy result on split graphs. T. Akiyama et al. (1980) have shown that HCYCLE is NP-complete on planar bipartite graphs with maximum degree 3. We use this result to show that HCYCLE is NP-complete for K 1 , 5 -free split graphs. Further, we present polynomial-time algorithms for Hamiltonian cycle in K 1 , 3 -free and K 1 , 4 -free split graphs. We believe that the structural results presented in this paper can be used to show similar dichotomy result for Hamiltonian path problem and other variants of Hamiltonian cycle (path) problems. [ABSTRACT FROM AUTHOR]

The existing helmet detection algorithms have disadvantages such as difficulty in detecting occluded targets, small targets, etc. To address those problems, a YOLO V4-based helmet detection improvement algorithm has been proposed. Firstly, the model's backbone structure is improved, and the backbone's multi-scale feature extraction capability is enhanced by using MCM modules with different sized convolutional kernels, the FSM channel attention module is used to guide the model to dynamically focus on the channel features of extracted small targets and obscured target information. Secondly, in order to optimize the model training, the latest loss function Eiou is used to replace Ciou for anchor frame regression prediction to improve the convergence speed and regression accuracy of the model. Finally, a helmet dataset is constructed from this paper, and a K-means clustering algorithm is used to cluster the helmet dataset and select the appropriate a priori candidate frames. The experimental results show that the improved algorithm has a significant improvement in detection accuracy compared with the original YOLO V4 algorithm, and can have a positive detection effect on small targets and obscured targets. [ABSTRACT FROM AUTHOR]

The goal of an outdegree-constrained edge-modification problem is to find a spanning subgraph or supergraph H of an input undirected graph G such that either: (Type I) the number of edges in H is minimized or maximized and H can be oriented to satisfy some specified constraints on the vertices' resulting outdegrees; or: (Type II) among all subgraphs or supergraphs of G that can be constructed by deleting or inserting a fixed number of edges, H admits an orientation optimizing some objective involving the vertices' outdegrees. This paper introduces eight new outdegree-constrained edge-modification problems related to load balancing called (Type I) MIN-DEL-MAX, MIN-INS-MIN, MAX-INS-MAX, and MAX-DEL-MIN and (Type II) p -DEL-MAX, p -INS-MIN, p -INS-MAX, and p -DEL-MIN. In each of the eight problems, the input is a graph and the goal is to delete or insert edges so that the resulting graph has an orientation in which the maximum outdegree (taken over all vertices) is small or the minimum outdegree is large. We first present a framework that provides algorithms for solving all eight problems in polynomial time on unweighted graphs. Next we investigate the inapproximability of the edge-weighted versions of the problems, and design polynomial-time algorithms for six of the problems on edge-weighted trees. [ABSTRACT FROM AUTHOR]

In this paper we address the question of synchronizing random automata in the critical settings of almost-group automata. Group automata are automata where all letters act as permutations on the set of states, and they are not synchronizing (unless they have one state). In almost-group automata, one of the letters acts as a permutation on n − 1 states, and the others as permutations. We prove that this small change is enough for automata to become synchronizing with high probability. More precisely, we establish that the probability that a strongly-connected almost-group automaton is not synchronizing is 2 k − 1 − 1 n 2 (k − 1) (1 + o (1)) , for a k -letter alphabet. We also present an efficient algorithm that decides whether a strongly-connected almost-group automaton is synchronizing. For a natural model of computation, we establish a O (k n) worst-case lower bound for this problem (O (n) for the average case), which is almost matched by our algorithm. [ABSTRACT FROM AUTHOR]

The Steiner tree problem is one of the fundamental and classical problems in combinatorial optimization. In this paper we study this problem in the CONGESTED CLIQUE model (CCM) [29] of distributed computing. For the Steiner tree problem in the CCM, we consider that each vertex of the input graph is uniquely mapped to a processor and edges are naturally mapped to the links between the corresponding processors. Regarding output, each processor should know whether the vertex assigned to it is in the solution or not and which of its incident edges are in the solution. We present two deterministic distributed approximation algorithms for the Steiner tree problem in the CCM. The first algorithm computes a Steiner tree using Õ (n 1 / 3) rounds and Õ (n 7 / 3) messages for a given connected undirected weighted graph of n nodes. Note here that Õ (⋅) notation hides polylogarithmic factors in n. The second one computes a Steiner tree using O (S + log log n) rounds and O (S m + n 2) messages, where S and m are the shortest path diameter and number of edges respectively in the given input graph. Both the algorithms achieve an approximation ratio of 2 (1 − 1 / ℓ) , where ℓ is the number of leaf nodes in the optimal Steiner tree. For graphs with S = ω (n 1 / 3 log n) , the first algorithm exhibits better performance than the second one in terms of the round complexity. On the other hand, for graphs with S = õ (n 1 / 3) , the second algorithm outperforms the first one in terms of the round complexity. In fact when S = O (log log n) then the second algorithm achieves a round complexity of O (log log n) and message complexity of Õ (n 2). To the best of our knowledge, this is the first work to study the Steiner tree problem in the CCM. [ABSTRACT FROM AUTHOR]

Transducers constitute a fundamental extension of automata. The class of regular word functions has recently emerged as an important class of word-to-word functions, characterized by means of (functional, or unambiguous, or deterministic) two-way transducers, copyless streaming string transducers, and MSO-definable graph transformations. A fundamental result in language theory is Kleene's Theorem, relating finite state automata and regular expressions. Recently, a set of regular function expressions has been introduced and used to prove a similar result for regular word functions, by showing its equivalence with copyless streaming string transducers. In this paper, we propose a direct, simplified and effective translation from unambiguous two-way transducers to regular function expressions extending the Brzozowski and McCluskey algorithm. In addition, our approach allows us to derive a subset of regular function expressions characterizing the (strict) subclass of functional sweeping transducers. [ABSTRACT FROM AUTHOR]

We consider an extension of tree automata on infinite trees that can use equality and disequality constraints between direct subtrees of a node. Recently, it has been shown that the emptiness problem for these kind of automata with a parity acceptance condition is decidable and that the corresponding class of languages is closed under Boolean operations. In this paper, we show that the class of languages recognizable by such tree automata with a Büchi acceptance condition is closed under projection. This construction yields a new algorithm for the emptiness problem, implies that a regular tree is accepted if the language is non-empty (for the Büchi condition), and can be used to obtain a decision procedure for an extension of monadic second-order logic with predicates for subtree comparisons. [ABSTRACT FROM AUTHOR]

A closed string contains a proper factor occurring as both a prefix and a suffix but not elsewhere in the string. Closed strings were introduced by Fici (WORDS 2011) as objects of combinatorial interest. This paper addresses a new problem by extending the closed string problem to the k -closed string problem, for which a level of approximation is permitted up to a number of Hamming distance errors, set by the parameter k. We address the problem of deciding whether or not a given string of length n over an integer alphabet is k -closed and additionally specifying the border resulting in the string being k -closed. Specifically, we present an 𝒪 (k n) -time and 𝒪 (n) -space algorithm to achieve this along with the pseudocode of an implementation and proof-of-concept experimental results. [ABSTRACT FROM AUTHOR]

Let (n = p q , e = n β) be an RSA public key with private exponent d = n δ , where p and q are large primes of the same bit size. At Eurocrypt 96, Coppersmith presented a polynomial-time algorithm for finding small roots of univariate modular equations based on lattice reduction and then succussed to factorize the RSA modulus. Since then, a series of attacks on the key equation e d − k ϕ (n) = 1 of RSA have been presented. In this paper, we show that many of such attacks can be unified in a single attack using a new notion called Coppersmith's interval. We determine a Coppersmith's interval for a given RSA public key (n , e). The interval is valid for any variant of RSA, such as Multi-Prime RSA, that uses the key equation. Then we show that RSA is insecure if δ < β + 1 3 α − 1 3 1 2 α β + 4 α 2 provided that we have approximation p 0 ≥ n of p with p − p 0 ≤ 1 2 n α , α ≤ 1 2. The attack is an extension of Coppersmith's result. [ABSTRACT FROM AUTHOR]

A connected dominating set (CDS, for short) for graph G is a dominating set which induces a connected subgraph of G. In this paper, we consider the problem of finding a minimum CDS for unit disk graphs, which have recently attracted considerable attention as a model of virtual backbone in multi-hop wireless networks. This optimization problem is known to be NP-hard and many approximation algorithms have been proposed in the literature. This paper proves a lower bound on the performance ratio of a greedy algorithm of Guha and Khuller which was originally proposed for general graphs and is known to be a representative in which the lookahead plays a crucial role in selecting a vertex to be contained in the CDS. More specifically, we show that for any fixed and integer , there is a unit disk graph with bounded degree consisting of at least vertices for which the output of the greedy algorithm is no better than times of an optimum solution to the same graph. [ABSTRACT FROM AUTHOR]

The exchanged crossed cube, denoted by E C Q (s , t) , is a novel interconnection network with fewer edges and smaller diameter compared to other variations of the corresponding hypercube. The linear array, denoted by L n , is one of the most popular topologies in optical networks. This paper addresses the routing and wavelength assignment for realizing E C Q (s , t) communication pattern on wavelength division multiplexing (WDM) optical network L n , where n = s + t + 1. We prove that the congestion for E C Q (s , t) on L n is equal to 2 s + t − 1 + ⌊ 2 t / 3 ⌋ , which is the lower bound of the minimum number of required wavelengths. In addition, an embedding scheme and an optimal wavelength assignment algorithm that achieve this bound are also proposed. [ABSTRACT FROM AUTHOR]

In this paper, we are interested in the runtime complexity of programs based on multiset rewriting. The motivation behind this work is the study of the complexity of chemistry-inspired programming models, which recently regained momentum due to their adequacy to large autonomous systems. In these models, data are most of the time left unstructured in a container, formally, a multiset. The program to be applied to this multiset is specified as a set of conditioned rules rewriting the multiset. At run time, these rewrite operations are applied concurrently, until no rule can be applied anymore (the set of elements they need cannot be found in the multiset anymore). A limitation of these models stand in their complexity: each computation step may require a complexity in where n denotes the number of elements in the multiset, and k is the size of the subset of elements needed to trigger a given rule. By analogy with chemistry, such elements can be called reactants. In this paper, we explore the possibility of improving the complexity of searching reactants through a static analysis of the rules' condition. In particular, we give a characterisation of this complexity, by analogy to the subgraph isomorphism problem. Given a rule R, we define its rank rk(R) and its calibre C(R), allowing us to exhibit an algorithm with a complexity in for searching reactants, while showing that and that most of the time. [ABSTRACT FROM AUTHOR]

The equivalence of finite automata and regular expressions dates back to the seminal paper of Kleene on events in nerve nets and finite automata from 1956. In the present paper we tour a fragment of the literature and summarize results on upper and lower bounds on the conversion of finite automata to regular expressions and vice versa. As an interesting special case also one-unambiguous regular expressions, a sort of a deterministic version of a regular expression, are considered. We also briefly recall the known bounds for the removal of spontaneous transitions ( ε-transitions) on non- ε-free nondeter-ministic devices. Moreover, we report on recent results on the average case descriptional complexity bounds for the conversion of regular expressions to finite automata and new developments on the state elimination algorithm that converts finite automata to regular expressions. [ABSTRACT FROM AUTHOR]

The generalized hypercube is a highly-connective network proposed by Bhuyan and Agrawal. In this paper, we study the restricted connectivity and fault-free unicast algorithm in the generalized hypercube. Firstly, we prove that the restricted connectivity of a r -dimensional generalized hypercube G (m r , m r − 1 , … , m 1) is 2 κ (G) − n , where κ (G) denotes the connectivity of G (m r , m r − 1 , … , m 1) and n = max { m 1 , m 2 , … , m r } , under the condition that each vertex has at least one fault-free neighbor. It is almost twice the traditional connectivity of G (m r , m r − 1 , … , m 1). Furthermore, we present an O (κ (G) 3) fault-free unicast algorithm in the generalized hypercube. [ABSTRACT FROM AUTHOR]

The problem of two node-disjoint paths is to identify two paths and from source to target without any common intermediate node in a communication network , where each node (vertex) in denotes a process and each edge denotes a communication channel between nodes and . In this paper, we present the first adaptive stabilizing algorithm for finding a pair of node-disjoint paths in a semi-anonymous arbitrary network in rounds and the state-space complexity is bits per process, where is the diameter of the communication network. The algorithm assumes weakly fair distributed daemon and the knowledge of an upper bound on the number of processes by each process. If two disjoint paths exist between and , two disjoint paths are guaranteed to be constructed. In addition, the algorithm detects if two node-disjoint paths exist or not. Since the proposed algorithm is stabilizing, it does not require initialization and is capable of withstanding transient faults. We view a fault that perturbs the state of the system but not its program as a transient fault. The proposed algorithm has a wide range of applications in ensuring reliability and security of sensor, mobile and fixed communication networks. [ABSTRACT FROM AUTHOR]

Interval routing is a space efficient method to realize a distributed routing function. In this paper we show that every circular-arc graph allows a shortest path strict 2-interval routing scheme, i.e., by introducing a global order on the vertices and assigning at most two (strict) intervals in this order to the ends of every edge allows to depict a routing function that implies exclusively shortest paths. Since circular-arc graphs do not allow shortest path 1-interval routing schemes in general, the result implies that the class of circular-arc graphs has strict compactness 2, which was a hitherto open question. Additionally, we show that the constructed 2-interval routing scheme is a 1-interval routing scheme with at most one additional interval assigned at each vertex and we outline an algorithm to calculate the routing scheme for circular-arc graphs in 풪( n2) time, where n is the number of vertices. [ABSTRACT FROM AUTHOR]

A classical theme in recursion theory is the question whether for a set A and n given elements x1,...,xn, an oracle machine having access to an oracle B can determine which of the elements xi belong to A. And if yes, how many queries are necessary? Here, B = A is possible and leads to interesting special cases of the general question In the present paper we adapt classical notions in this area of bounded query computations to real number algorithms as formalized by Blum, Shub, and Smale and analyze them in the new framework. Among the results obtained we find: A real version of a non-speedup theorem based on real quantifier elimination, some basic properties about selective real sets, and a way to construct natural terse sets in ℝ by applying the implicit function theorem. The purpose of the paper is on presenting some interesting questions and basic results as an appertizer to intensify research into this direction. [ABSTRACT FROM AUTHOR]

In this paper, we study to what extent decidability is connected to universality. A natural context for such a study is provided by the axiomatic theory of computability, automata and algorithms. In Section 2, we introduce necessary concepts, constructions, axioms, postulates, conditions and problems. Section 3 contains the main results of the paper. In particular, it is demonstrated (Theorems 1 and 2) that undecidability of algorithmic problems does not depend on existence of universal algorithms and may be caused by weaker conditions. At the same time, results of Theorems 2 and 3 demonstrate that decidability is incompatible with universality. It is also proved (Theorem 5) that sufficiently big classes of total algorithms/automata, such as the class of all primitive recursive functions, cannot have universal algorithms/automata. [ABSTRACT FROM AUTHOR]

In this paper, we introduce some basic measures for insertion-deletion system and matrix insertion-deletion system. These measures are based on the number of variables, the number of productions and the number of symbols in a grammar. We show that with respect to these measures, both the systems are more succinct over context-free grammars in representing certain families of context-free languages. [ABSTRACT FROM AUTHOR]

In this paper we consider the problem of computing the longest common abelian factor (LCAF) between two given strings. We present a simple time algorithm, where n is the length of the strings and is the alphabet size, and a sub-quadratic running time solution for the binary string case, both having linear space requirement. Furthermore, we present a modified algorithm applying some interesting tricks and experimentally show that the resulting algorithm runs faster. [ABSTRACT FROM AUTHOR]

A feedback vertex/arc set (abbreviated as FVS/FAS) of a graph is a subset of the vertices/arcs which contains at least one vertex/arc for every cycle of that graph. A minimum FVS/FAS is an FVS/FAS which contains the smallest number of vertices/arcs. Hsu et al. [11] first proposed an algorithm which can find a minimum FVS in a rotator graph. In this paper, we present a formula for finding an FAS for a rotator graph and prove that the FAS is minimum. This formula can be easily implemented by an efficient algorithm which obtains a minimum FAS in a rotator graph. Finally, we also present a concise formula for finding a minimum FAS in an incomplete rotator graph in this paper. [ABSTRACT FROM AUTHOR]

In this paper we consider the computational complexity of deciding the existence of a perfect matching in certain classes of dense k-uniform hypergraphs. It has been known that the perfect matching problem for the classes of hypergraphs H with minimum ((k - 1)-wise) vertex degreeδ(H) at least c|V(H)| is NP-complete for $c < \frac{1}{k}$ and trivial for c ≥ ½, leaving the status of the problem with c in the interval $[\frac{1}{k}, \frac{1}{2})$ widely open. In this paper we show, somehow surprisingly, that ½ is not the threshold for tractability of the perfect matching problem, and prove the existence of an ε > 0 such that the perfect matching problem for the class of hypergraphs H with δ(H) ≥ (½ - ε)|V(H)| is solvable in polynomial time. This seems to be the first polynomial time algorithm for the perfect matching problem on hypergraphs for which the existence problem is nontrivial. In addition, we consider parallel complexity of the problem, which could be also of independent interest. [ABSTRACT FROM AUTHOR]

The class of finite Sturmian words consists of words having particularly simple compressed representation, which is a generalization of the Fibonacci recurrence for Fibonacci words. The subword graphs of these words (especially their compacted versions) have a very special regular structure. In this paper we investigate this structure in more detail than in previous papers and show how several syntactical properties of Sturmian words follow from their graph properties. Consequently simple alternative graph-based proofs of several known facts are presented. The very special structure of subword graphs leads also to special easy algorithms computing some parameters of Sturmian words: the number of subwords, the critical factorization point, lexicographically maximal suffixes, occurrences of subwords of a fixed length, and right special factors. These algorithms work in linear time with respect to n, the size of the compressed representation of the standard word, though the words themselves can be of exponential size with respect to n. Some of the computed parameters can be also of exponential size, however we provide their linear size compressed representations. We introduce also a new concept related to standard words: Ostrowski automata. [ABSTRACT FROM AUTHOR]

The graph isomorphism problem is to check if two given graphs are isomorphic. Graph isomorphism is a well studied problem and numerous algorithms are available for its solution. In this paper we present algorithms for graph isomorphism that employ the spectra of graphs. An open problem that has fascinated many a scientist is if there exists a polynomial time algorithm for graph isomorphism. Though we do not solve this problem in this paper, the algorithms we present take polynomial time. These algorithms have been tested on a good collection of instances. However, we have not been able to prove that our algorithms will work on all possible instances. In this paper, we also give a new construction for cospectral graphs. [ABSTRACT FROM AUTHOR]

In this paper two concurrent versions of Brzozowski's deterministic finite automaton (DFA) construction algorithm are developed from first principles, the one being a slight refinement of the other. We rely on Hoare's CSP as our notation. The specifications that are proposed of the Brzozowski algorithm are in terms of the concurrent composition of a number of top-level processes, each participating process itself composed of several other concurrent processes. After considering a number of alternatives, this particular overall architectural structure seemed like a natural and elegant mapping from the sequential algorithm's structure. While we have carefully argued the reasons for constructing the concurrent versions as proposed in the paper, there are of course, a large range of alternative design choices that could be made. There might also be scope for a more fine-grained approach to updating sets or checking for similarity of regular expressions. At this stage, we have chosen to abstract away from these considerations, and leave their exploration for a subsequent step in our research. [ABSTRACT FROM AUTHOR]

In this research, a framework is proposed for answering the question: whether a dominant sequence exists for the multiple self-contained input streams destined for a computation provider running the requested applications concurrently. The framework is extended to find an optimal semidominant sequence for multiple input streams. This paper also shows that an existent universal dominant sequence can be formed by permuting a set of dominant input streams. In this paper, the neighbor-connected graph is first proposed to model the sequence problem of multiple input streams. Then, an algorithm with time complexity O(nLn) is proposed to determine the existence of a dominant data-receiving sequence, where L is the maximal length of the input streams plus one and n is the number of input streams. Examples of applying the framework to solve the sequence problems for several computation-intensive applications are also given. Furthermore, the framework is extended to find an optimal semidominant sequence using an algorithm with time complexity O(nLnlogδ*), where δ* is the maximal degree that the sequence diverges from all the optimal subsequences. Finally, the property of a universal dominant sequence is studied and the performance of the sequence is compared with those of other sequences. [ABSTRACT FROM AUTHOR]

Degenerate primers are used to amplify a given set of genomic sequences using a technique called Multiplex Polymerase Chain Reaction (MP-PCR). The problem of minimizing the number of degenerate primers required to amplify a given set of DNA sequences, also known as the Degenerate Primer Design Problem (DPDP), has been extensively studied in the literature and proven to be NP-Complete. In this paper we present efficient algorithms for solving DPDP. For example, one of the algorithms we give in this paper is iterative and has a runtime of O(b|Σ|log|Σ|dn2mp) to select a set of p degenerate primers, each of given length l and degeneracy at most d, for n sequences each of length m in the input, the number of candidates retained in each iteration being b. Σ is the alphabet of the input strings. This is an improvement over the runtime of the best known prior algorithm, MIPS by Souvenir et al. [15], which has a runtime of O(bn3mp). We provide an experimental comparison of MIPS and our algorithms. [ABSTRACT FROM AUTHOR]

This paper presents an exhaustive analysis of the problem of computing the Lp distance of two probabilistic automata. It gives efficient exact and approximate algorithms for computing these distances for p even and proves the problem to be NP-hard for all odd values of p, thereby completing previously known hardness results. It further proves the hardness of approximating the Lp distance of two probabilistic automata for odd values of p. Similar techniques to those used for computing the Lp distance also yield efficient algorithms for computing the Hellinger distance of two unambiguous probabilistic automata both exactly and approximately. A problem closely related to the computation of a distance between probabilistic automata is that of testing their equivalence. This paper also describes an efficient algorithm for testing the equivalence of two arbitrary probabilistic automata A1 and A2 in time O(|Σ|(|A1| + |A2|)3), a significant improvement over the previously best reported algorithm for this problem. [ABSTRACT FROM AUTHOR]

This paper studies the problem of orienting all edges of a weighted graph such that the maximum weighted outdegree of vertices is minimized. This problem, which has applications in the guard arrangement for example, can be shown to be $\mathcal{NP}$-hard generally. In this paper we first give optimal orientation algorithms which run in polynomial time for the following special cases: (i) the input is an unweighted graph, and (ii) the input graph is a tree. Then, by using those algorithms as sub-procedures, we provide a simple, combinatorial, $\min \{\frac{w_{max}}{w_{min}},(2 - \varepsilon)\}$-approximation algorithm for the general case, where wmax and wmin are the maximum and the minimum weights of edges, respectively, and ε is some small positive real number that depends on the input. [ABSTRACT FROM AUTHOR]

In this paper, we discuss a simple, Monte Carlo algorithm for the problem of checking whether a Quantified Boolean Formula (QBF) in Conjunctive Normal Form (CNF), with at most two literals per clause has a model. The term k-CNF is used to describe boolean formulas in CNF, with at most /c literals per clause and the problem of checking whether a given k-CNF formula is satisfiable is called the k-SAT problem. A QBF is a boolean formula, accompanied by a quantifier string which imposes a linear ordering on the variables of that formula. The problem of finding a model for a QBF formula in CNF, with at at most k literals per clause is called the QkSAT problem. The QkSAT problem is PSPACE-complete, for k ≥ 3. However, the Q2SAT problem can be decided in polynomial time; the graph-based procedure, discussed in [1], is the first such algorithm for this problem. This procedure requires the construction of a global implication graph, corresponding to the input formula and searching for certain paths in this graph. Hence the complete set of clauses must be part of the input. We propose an incremental, randomized approach for the Q2SAT problem that is essentially local in nature, in that the complete clausal set need not be provided at any time, in the presence of a verifier. We show that the randomized algorithm can be analyzed as a one-dimensional random walk, with one reflecting barrier and one absorbing barrier. On a Q2SAT instance with in clauses on n variables, our coin-flipping algorithm runs in time O(n² V(m, n)), where V(m, n) is the time required to verify that a given model satisfies the formula. Additionally, if the instance is satisfiable, the probability that our algorithm fails to find a model is less than one half. The design and analysis of a randomized algorithm for a problem, is important from both the theoretical and the practical perspectives. Randomized approaches tend to be simple and elegant, thereby making the process of checking correctness, effortless as well. The randomized approach discussed in this paper lays the groundwork for analyzing a number of problems related to 2CNF formulas and directed graphs. We remark that our work in this paper is the first randomized algorithm for a class of QBFs. [ABSTRACT FROM AUTHOR]

Ant Colony Optimization (ACO) techniques can be successfully implemented to solve many combinatorial optimization problems. After the traveling salesman problem was successfully solved using the ACO technique, other researchers have concentrated on solving other problems like the quadratic assignment and the job-shop scheduling problems using the same technique. In this paper we use the ACO technique to route messages through an N×N Optical Multistage Interconnection Network (OMIN) allowing upto 'C' limited crosstalk's (conflicts between messages within a switch) where 'C' is a technology driven parameter and is always less than log2N. Messages with switch conflicts satisfying the crosstalk constraint are allowed to pass in the same group, but if there is any link conflict, then messages have to be routed in a different group. The focus is to minimize the number of passes required for routing allowing upto 'C' limited crosstalks in an N×N optical network. This routing problem is an NP-hard problem. In this paper we show how the ACO technique can be applied to the routing problem and compare the performance of the ACO technique to that of the degree-descending algorithm using simulation techniques. Finally the lower bound estimate on the minimum number of passes required is calculated and compared to the results obtained using the two algorithms discussed. The results obtained show that the ACO technique performs better than the degree-descending algorithm and is quite close to optimal algorithms to the problem. [ABSTRACT FROM AUTHOR]

This paper proposes a procedure to design fault tolerant algorithms for the R-Mesh and some of its restrictive variations. This procedure first identifies a healthy sub-mesh from a faulty model using the bypass and removal fault model. Then it uses scalable algorithms to simulate the larger faulty model on the resulting healthy sub-mesh. The algorithms for the bypass model tolerates n faults in an n×n R-Mesh (LR-Mesh) and runs in O(T log n) (O(T)) time, where T is the execution time on the original mesh without faults. For the removal model, we design fault tolerant algorithms for some interesting variations of the R-Mesh, specifically, the NXR-Mesh and the NXLR-Mesh. We propose the first scaling simulations for these models and present a simulation of the R-Mesh on the NXR-Mesh. The results of this paper enable us to consider certain reconfigurable models in a more practical environment than previously allowed. [ABSTRACT FROM AUTHOR]

Partitioned Optical Passive Stars (POPS) network has been presented recently as a desirable model of parallel computation. Several papers have been published that address fundamental problems on this architecture. The algorithms presented in this paper are valid for POPS(d,g) where d>g and use randomization. We present an algorithm that solves the problem of sparse enumeration sorting of d∊ keys in $\widetilde O(\frac{d}{g}\rceil+\log g)$ time and hence performs better than previous algorithms. We also present algorithms that allow us to do stable sorting of integers in the range [1,log n] and $[1, \frac{d}{g}]$ in $\widetilde O(\lceil \frac{d}{g}\rceil+\log n)$ time. When g=n∊, for any constant 0<∊<½ this allows us to do sorting of integers in the range [1,n] in $\widetilde O(\frac{1}{1-2\epsilon}(\lceil\frac{d}{g}\rceil+\log g))$ time. We finally use these algorithms to solve the problem of multiple binary search in the case where we have d∊ keys in $\widetilde O(\frac{d}{g}+\log g)$ time and in the case where we have integer keys in the range [1,n] in $\widetilde O(\frac{1}{1- 2\epsilon}(\lceil\frac{d}{g}\rceil+\log g))$ time, when g=n∊, for some constant 0<∊<½. [ABSTRACT FROM AUTHOR]

This paper addresses multicasting and broadcasting in undirected WDM networks and QoS extensions of multicasting. It is given an undirected network G=(V, E), with Λ is the set of the available wavelengths in G, and associated with each edge, there is a subset of wavelengths on it. For a multicast request r=(s, D) with a source s and a set D of destinations, it is to find a tree rooted at s including all nodes in D such that the cost of the tree is minimized in terms of the cost of wavelength conversion at nodes and the cost of using wavelength on edges. This paper proves that multicasting in this model of networks is NP-Hard and cannot be approximated within a constant factor, unless P=NP. Furthermore, an auxiliary graph is constructed for the original WDM network, the multicasting is reduced to a group Steiner tree problem on the auxiliary graph and an approximate algorithm based on the group Steiner tree algorithm proposed by M. Charikar et al. with performance ratio of O(log[sup 2](nk) log log(nk) log p) is provided, where k=|Λ| and p=|D∪{s}|. At last, some QoS extensions of multicasting are discussed. [ABSTRACT FROM AUTHOR]

Chandra and Toueg proposed in 1993 a new approach to overcome the impossibility of reaching deterministically Consensus — and by corollary Atomic Broadcast — in asynchronous systems subject to crash failures. They augment the asynchronous system with a possibly Unreliable Failure Detector which provides some information about the operational state of processes. In this paper, we present an extension of the Consensus problem that we call Uniform Prefix Agreement. This extension enables all the processes to propose a flow of messages during an execution — instead of one as in the Consensus problem — and uses all these proposed messages to compose the decision value. Prefix Agreement is based on an Unreliable Failure Detector. We use repeated executions of Prefix Agreement to build an efficient Uniform Atomic Broadcast algorithm. This paper describes the Uniform Prefix Agreement and Uniform Atomic Broadcast algorithms, and provides proofs of their correctness. [ABSTRACT FROM AUTHOR]

Heterogeneous multiprocessor architectures allow embedded real-time systems to better match computing resources to each application's needs and dynamic workload requirements, thereby providing many opportunities for improved performance with reduced power consumption. Unfortunately, guaranteeing real-time requirements on heterogeneous multiprocessors remains a critical problem due to the lack of appropriate scheduling algorithms and analysis methods. In this paper, we consider EDZL (Earliest Deadline First until Zero-Laxity) for performance asymmetric multiprocessor scheduling. EDZL has been shown to outperform other scheduling policies such as global EDF on identical multiprocessors. We show that EDZL is still effective on performance asymmetric multi-processors, and present an efficient EDZL schedulability test. Experimental results show that EDZL scheduling is able to schedule up to 20% more task sets than global EDF and that our new EDZL schedulability test can accept up to 30% more schedulable task sets than a presently exiting one. [ABSTRACT FROM AUTHOR]

In this paper, a self-stabilizing algorithm is presented for finding the articulation points of a connected undirected graph on a distributed or network model of computation after O(n[SUP2]&verbar;E&verbar;) moves. The algorithm is resilient to transient faults and does not require initialization. A correctness proof of the algorithm is also presented. The paper concludes with remarks on issues such as the time complexity of the algorithm and open problems. [ABSTRACT FROM AUTHOR]

Highly dynamic networks rarely offer end-to-end connectivity at a given time. Yet, connectivity in these networks can be established over time and space, based on temporal analogues of multi-hop paths (also called journeys). Attempting to optimize the selection of the journeys in these networks naturally leads to the study of three cases: shortest (minimum hop), fastest (minimum duration), and foremost (earliest arrival) journeys. Efficient centralized algorithms exists to compute all cases, when the full knowledge of the network evolution is given. In this paper, we study the distributed counterparts of these problems, i.e. shortest, fastest, and foremost broadcast with termination detection (TDB), with minimal knowledge on the topology. We show that the feasibility of each of these problems requires distinct features on the evolution, through identifying three classes of dynamic graphs wherein the problems become gradually feasible: graphs in which the re-appearance of edges is recurrent (class ), bounded-recurrent (), or periodic (), together with specific knowledge that are respectively n (the number of nodes), Δ (a bound on the recurrence time), and p (the period). In these classes it is not required that all pairs of nodes get in contact - only that the overall footprint of the graph is connected over time. Our results, together with the strict inclusion between , , and , implies a feasibility order among the three variants of the problem, i.e. TDB[ foremost] requires weaker assumptions on the topology dynamics than TDB[ shortest], which itself requires less than TDB[ fastest]. Reversely, these differences in feasibility imply that the computational powers of , , and also form a strict hierarchy. [ABSTRACT FROM AUTHOR]

In this paper, we propose two new self-stabilizing algorithms, MWCDS-C and MWCDS-D, for minimal weakly connected dominating sets in an arbitrary connected graph. Algorithm MWCDS-C stabilizes in O(n4) steps using an unfair central daemon and space requirement at each node is O(log n) bits at each node for an arbitrary connected graph with n nodes; it uses a designated node while other nodes are identical and anonymous. Algorithm MWCDS-D stabilizes using an unfair distributed daemon with identical time and space complexities, but it assumes unique node IDs. In the literature, the best reported stabilization time for a minimal weakly connected dominating set algorithm is O(nmA) under a distributed daemon [1], where m is the number of edges and A is the number of moves to construct a breadth-first tree. [ABSTRACT FROM AUTHOR]

This paper describes a random model for chemical graphs that captures the notion of valence along with algorithms to generate chemical graphs using this model. An approach for computing the probability that a particular chemical graph is generated under this model is provided. The model is also used to provide theoretical bounds on the accuracy of a class of canonical labeling algorithms for a class of hydrocarbons. [ABSTRACT FROM AUTHOR]

This paper describes a failure scenario in the known self-stabilizing algorithm for knot detection in directed graphs, occurring due to incorrect computation of certain variables. A modified algorithm is proposed, which overcomes the shortcomings of the known algorithm. [ABSTRACT FROM AUTHOR]

This paper introduces a new disambiguation algorithm for finite automata and functional finite-state transducers. It gives a full description of this algorithm, including a detailed pseudocode and analysis, and several illustrating examples. The algorithm is often more efficient and the result dramatically smaller than the one obtained using determinization for finite automata or the construction of Schützenberger. The unambiguous automaton or transducer created by our algorithm are never larger than those generated by the construction of Schützenberger. In fact, in a variety of cases, the size of the unambiguous transducer returned by our algorithm is only linear in that of the input transducer while the transducer created by the construction of Schützenberger is exponentially larger. Our algorithm can be used effectively in many applications to make automata and transducers more efficient to use. [ABSTRACT FROM AUTHOR]

The random (2 + p)-SAT model has been proposed [18] to study the possible relation between the 'order' of phase transitions and computational complexity. It was also claimed that there exists pc > 0, such that for p < pc the random (2 + p)-SAT instance behaves like 2-SAT. Later, Achlioptas et al. [3] obtained the first rigorous results that 0.4 ≤ pc ≤ 0.695, the methods they use are the first moment method and the simple Unit-Clause algorithm. In this paper, we try to optimize the local maximality condition of the truth assignments when implementing the first moment method. We prove that the phase transition point of clauses-to-variables ratio r (dependent on p) can be improved. Moreover, we show that the upper bound of pc can be reduced to 0.6846. This fact implies that, for a constant λ < 1, a random (2 + p)-SAT formula with λn 2-clauses and 2.17 n 3-clauses is almost surely unsatisfiable. [ABSTRACT FROM AUTHOR]

Min-degree constrained minimum spanning tree (md-MST) problem is an NP-hard combinatorial optimization problem seeking for the minimum weight spanning tree in which the vertices are either of degree one (leaf) or at least degree d > 2. md-MST problem is new to the literature and very few studies have been conducted on this problem in deterministic graph. md-MST problem has several appealing real-world applications. Though in realistic applications the graph conditions and parameters are stochastic and vary with time, to the best of our knowledge no work has been done on solving md-MST problem in stochastic graph. This paper proposes a decentralized learning automata-based algorithm for finding a near optimal solution to the md-MST problem in stochastic graph. In this work, it is assumed that the weight associated with the graph edge is random variable with a priori unknown probability distribution. This assumption makes the md-MST problem incredibly harder to solve. The proposed algorithm exploits an intelligent sampling technique avoiding the unnecessary samples by focusing on the edges of the min-degree spanning tree with the minimum expected weight. On the basis of the Martingale theorem, the convergence of the proposed algorithm to the optimal solution is theoretically proven. Extensive simulation experiments are performed on the stochastic graph instances to show the performance of the proposed algorithm. The obtained results are compared with those of the standard sampling method in terms of the sampling rate and solution optimality. Simulation experiments show that the proposed method outperforms the standard sampling method. [ABSTRACT FROM AUTHOR]

For a connected non-complete graph, a vertex separator is a subset of vertices whose deletion increases the number of connected components and the vertex connectivity of the graph refers to the size of a minimum vertex separator. A graph with the vertex con-nectivity fc is said to be k-vertex connected. Given a fc-vertex connected graph G, vertex connectivity augmentation determines a smallest set of edges whose augmentation to G makes it (k + l)-vertex connected. In this paper, we report our study on connectiv-ity augmentation in 1-connected graphs, 2-connected graphs, and fc-connected chordal graphs. We first represent the graph under consideration using a "tree-like" graph. This tree is unique and explicitly captures the connectivity information of the graph. Using this tree, our proposed data structure maintains the set of equivalence classes based on an equivalence relation on the set of leaves of the tree. This partition determines a set of edges to be augmented to increase the connectivity of the graph by one. Based on our data structure, we present a new combinatorial analysis and an elegant proof of correctness of our linear-time algorithm for an optimum connectivity augmentation. The novelty is in the data structure which is a unified framework for all three augmentations. As far as the run-time analysis is concerned, given the associated tree, our approach yields an augmentation set in linear time. [ABSTRACT FROM AUTHOR]

Algorithmic combinatorics on partial words, or sequences of symbols over a finite alphabet that may have some do-not-know symbols or holes, has been developing in the past few years. Applications can be found, for instance, in molecular biology for the sequencing and analysis of DNA, in bio-inspired computing where partial words have been considered for identifying good encodings for DNA computations, and in data compression. In this paper, we focus on two areas of algorithmic combinatorics on partial words, namely, pattern avoidance and subword complexity. We discuss recent contributions as well as a number of open problems. In relation to pattern avoidance, we classify all binary patterns with respect to partial word avoidability, we classify all unary patterns with respect to hole sparsity, and we discuss avoiding abelian powers in partial words. In relation to subword complexity, we generate and count minimal Sturmian partial words, we construct de Bruijn partial words, and we construct partial words with subword complexities not achievable by full words (those without holes). [ABSTRACT FROM AUTHOR]

In this paper we describe a "light" algorithm for the on-line construction of a small automaton recognising a finite set of words. The algorithm runs in linear time. We carried out good experimental results on real dictionaries, on biological sequences and on the sets of suffixes (resp. factors) of a set of words that shows how our automaton is near to the minimal one. For the suffixes of a text, we propose a modified construction that leads to an even smaller automaton. We moreover construct linear algorithms for the insertion and deletion of a word in a finite set, directly from the constructed automaton. [ABSTRACT FROM AUTHOR]