Search

We consider the problem of computing the diameter of a unicycle graph (i.e., a graph with a unique cycle). We present an O (n) time algorithm for the problem, where n is the number of vertices of the graph. This improves the previous best O (n log ⁡ n) time solution [Oh and Ahn, ISAAC 2016]. Using this algorithm as a subroutine, we solve the problem of adding a shortcut to a tree so that the diameter of the new graph (which is a unicycle graph) is minimized; our algorithm takes O (n 2 log ⁡ n) time and O (n) space. The previous best algorithms solve the problem in O (n 2 log 3 ⁡ n) time and O (n) space [Oh and Ahn, ISAAC 2016], or in O (n 2) time and O (n 2) space [Bilò, ISAAC 2018]. • The paper presents a linear time algorithm for computing the diameter of unicycle graphs. • The paper gives a new algorithm which finds a new edge to add to a tree so that the diameter of the new graph is minimized. • The algorithms rely on certain domination relations among edges of the graphs. [ABSTRACT FROM AUTHOR]

In this paper, we revisit the r -gathering problem. Given sets C and F of points on the plane and distance d (c , f) for each c ∈ C and f ∈ F , an r -gathering of C to F is an assignment A of C to open facilities F ′ ⊆ F such that r or more members of C are assigned to each open facility. The cost of an r -gathering is max c ∈ C ⁡ d (c , A (c)). The r -gathering problem computes the r -gathering minimizing the cost. In this paper we study the r -gathering problem when C and F are on a line and present a O (| C | + | F |) -time algorithm to solve the problem. Our solution is optimal since any algorithm needs to read C and F at least once. [ABSTRACT FROM AUTHOR]

Branchings play an important role in digraph theory and algorithms. In particular, a chapter in the monograph of Bang-Jensen and Gutin, Digraphs: Theory, Algorithms and Application, Ed. 2, 2009 is wholly devoted to branchings. The well-known Edmonds Branching Theorem provides a characterization for the existence of k arc-disjoint out-branchings rooted at the same vertex. A short proof of the theorem by Lovász (1976) leads to a polynomial-time algorithm for finding such out-branchings. A natural related problem is to characterize digraphs having an out-branching and an in-branching which are arc-disjoint. Such a pair of branchings is called a good pair. Bang-Jensen, Bessy, Havet and Yeo (2022) pointed out that it is NP-complete to decide if a given digraph has a good pair. They also showed that every digraph of independence number at most 2 and arc-connectivity at least 2 has a good pair, which settled a conjecture of Thomassen for digraphs of independence number 2. Then they asked for the smallest number n n g p of vertices in a 2-arc-strong digraph which has no good pair. They proved that 7 ≤ n n g p ≤ 10. In this paper, we prove that n n g p = 10 , which solves the open problem. • The study of good pair has relations with Tutte's Packing Theorem and Edmonds Branching Theorem. • We answer a problem by Bang-Jensen, Bessy, Havet and Yeo about the minimum order of 2-arc-strong digraphs without good pairs. • We study the relationship between Hamilton dipath and good pair. • We generalize some results by Bang-Jensen, Bessy, Havet and Yeo on good pair. [ABSTRACT FROM AUTHOR]

We consider the problem of augmenting an n -vertex tree with one shortcut in order to minimize the diameter of the resulting graph. The tree is embedded in an unknown space and we have access to an oracle that, when queried on a pair of vertices u and v , reports the weight of the shortcut (u , v) in constant time. Previously, the problem was solved in O (n 2 log 3 ⁡ n) time for general weights [Oh and Ahn, ISAAC 2016], in O (n 2 log ⁡ n) time for trees embedded in a metric space [Große et al. , Int. J. FCS], and in O (n log ⁡ n) time for paths embedded in a metric space [Wang, Comput. Geom.]. Very recently an algorithm for general weights requiring O (n 2 log ⁡ n) time and O (n) space has been developed [Wang and Zhao, Theor. Comp. Science]. Finally, a (1 + ε) -approximation algorithm running in O (n + 1 / ε 3) has been designed for paths embedded in R d , for constant values of d [Große et al. , Int. J. FCS]. In this paper we design an asymptotic time-optimal algorithm for trees and general edge-weights that requires O (n 2) time and O (n log ⁡ n) space. Moreover, for trees embedded in a metric space, we design (i) an exact O (n log ⁡ n) -time algorithm and (ii) a (1 + ε) -approximation algorithm that runs in O (n + ε − 1 log ⁡ ε − 1) time. [ABSTRACT FROM AUTHOR]

In this paper, we revisit the problem of computing longest common almost increasing subsequence (LCAIS) where, given two input sequences, the goal is to compute a common subsequence that is 'almost' increasing. Here the concept of an almost increasing subsequence offers an interesting relaxation over the increasing condition. This problem has been studied in the literature albeit with some constraints. Here, we present a number of a number of algorithmic approaches to solve the problem more generally and efficiently. [ABSTRACT FROM AUTHOR]

Motivated by the design of cost-efficient communication networks, the problem about Maximum Internal Spanning Tree that arises in a connected graph, is proposed to find a spanning tree with the maximum number of internal vertices. In 2018, Xingfu Li et al. presented a polynomial algorithm to find a maximum internal spanning tree in a connected interval graph. Based on the structure of normal orderings on interval graphs, we present a simple linear time algorithm that solve the problem when restricted to connected interval graphs in this paper. The proof provides additional insight about the linear time algorithm on interval graphs. • The MIST problem is solvable in a simple linear time algorithm under the restriction of connected interval graphs. • The structure of normal orderings on interval graphs is proposed to solve the Maximum Internal Spanning Tree problem. • The proof of the main results is more easy to understand with proper cases to prove. [ABSTRACT FROM AUTHOR]

Abstract In this paper, we consider the problems for covering multiple intervals on a line. Given a set B of m line segments (called "barriers") on a horizontal line L and another set S of n horizontal line segments of the same length in the plane, we want to move all segments of S to L so that their union covers all barriers and the maximum movement of all segments of S is minimized. Previously, an O (n 3 log ⁡ n) -time algorithm was given for the case m = 1. In this paper, we propose an O (n 2 log ⁡ n log ⁡ log ⁡ n + n m log ⁡ m) -time algorithm for a more general setting with any m ≥ 1 , which also improves the previous work when m = 1. We then consider a line-constrained version of the problem in which the segments of S are all initially on the line L. Previously, an O (n log ⁡ n) -time algorithm was known for the case m = 1. We present an algorithm of O (m log ⁡ m + n log ⁡ m log ⁡ n) time for any m ≥ 1. These problems may have applications in mobile sensor barrier coverage in wireless sensor networks. [ABSTRACT FROM AUTHOR]

Given two sequences A and B of lengths m and n , respectively, the consecutive suffix alignment (CSA) problem is to compute the longest common subsequence (LCS) between A and each suffix of B. The data structure of two-dimensional matrix for solving the CSA problem is named S-table. The S-table would be infeasible due to its quadratic-space requirement for long sequences. The linear-space S-table, proposed by Alves et al. (2005), consists of the first row of the S-table and the changes between every two consecutive rows. However, there is no further discussions and practical applications for the linear-space S-table. This paper proposes algorithms for improving three problems, related to LCS and S-table, by using the linear-space S-table. Suppose that A = A (1) A (2) (concatenation of two substrings), and we are given the S-table of A (2) and B , as well as the alignment result (LCS length) of A (1) to each prefix of B. The concatenated LCS (CoLCS) problem is to find the alignment result of A and B. For the CoLCS problem, this paper proposes an O(n)-time algorithm with the technique of set union-find to achieve the linear space. Next, for merging two linear S-tables, we propose an O (n log ⁡ n) -time algorithm with the technique of range query and update to improve the quadratic-time algorithm using quadratic-space S-tables. Then, we propose an O(n)-time algorithm to update the linear-space S-table of A and B to obtain the linear-space S-table of Aσ and B , where σ denotes a new character appended to the tail of A. For further applications to long sequences by using the linear-space S-table, the algorithms proposed in this paper are essential and necessary. [ABSTRACT FROM AUTHOR]

The longest common palindromic subsequence (LCPS) problem is a variant of the longest common subsequence (LCS) problem. Given two input sequences A and B , the LCPS problem is to find the common subsequence of A and B such that the answer is a palindrome with the maximal length. The LCPS problem was first proposed by Chowdhury et al. (2014) [9] , who proposed a dynamic programming algorithm with O (m 2 n 2) time, where m and n denote the lengths of A and B , respectively. This paper proposes a diagonal-based algorithm for solving the LCPS problem with O (L (m − L) R log ⁡ n) time and O (R L) space, where R denotes the number of match pairs between A and B , and L denotes the LCPS length. In our algorithm, the 3-dimensional minima finding algorithm is invoked to overcome the domination problem. As experimental results show, our algorithm is efficient practically compared with some previously published algorithms. [ABSTRACT FROM AUTHOR]

A new algorithm is proposed in this paper for computing the nearest polynomial to multiple given polynomials with a given zero in the real case, where the distance between polynomials is defined by the weighted ℓ 2 , q norm (0 < q ≤ 2). First, the problem is formulated as a univariate constrained non-convex minimization problem, where prior information of the coefficients of the polynomial can be embedded by selecting proper weights. Then, an iteratively reweighted algorithm is designed to solve the obtained problem, and also the convergence and rate of convergence are uniformly demonstrated for all q in (0 , 2 ]. Since all the existing methods for computing the nearest polynomial to multiple given polynomials with a given zero are limited to the real case, we ingeniously extend the results to the complex case. Finally, two representative examples that separately compute the nearest real and complex polynomials are presented to show the effectiveness of the proposed algorithm. • A weighted ℓ 2 , q -norm based minimization problem is constructed with prior information of polynomial embedded. • After converting the problem into a univariate problem, an iteratively reweighted algorithm is proposed to solve it. • Using properties of a concave function, convergence and rate of convergence of the proposed algorithm are provided. • It is the first time to study computation of the nearest polynomial to multiple given polynomials with a given zero in the complex case. [ABSTRACT FROM AUTHOR]

This article explores an interplay between process crash failures and concurrency. Namely, it aims at answering the question, "Is it possible to cope with more crash failures when some number of crashes occur before some predefined contention point happened?". These crashes are named λ-constrained crashes , where λ is the predefined contention point (known by the processes). Hence, this article considers two types of process crashes: λ -constrained crashes and classical crashes (which can occur at any time and are consequently called any-time crashes). Considering a system made up of n asynchronous processes communicating through atomic read/write registers, the article focuses on the design of two agreement-related algorithms. Assuming λ = n − 1 and no any-time failure, the first algorithm solves the consensus problem in the presence of one λ -constrained crash failure, thereby circumventing the well-known FLP impossibility result. The second algorithm considers k -set agreement for k ≥ 2. It is a k -set agreement algorithm such that λ = n − ℓ and ℓ ≥ k = m + f that works in the presence of up to (2 m + ℓ − k) λ -constrained crashes and (f − 1) any-time crashes, i.e., up to t = (2 m + ℓ − k) + (f − 1) process crashes. It follows that considering the timing of failures with respect to a predefined contention point enlarges the space of executions in which k -set agreement can be solved despite the combined effect of asynchrony, concurrency, and process crashes. The paper also presents agreement-related impossibility results for consensus and k -set agreement in the context of λ -constrained process crashes (with or without any-time crashes). [ABSTRACT FROM AUTHOR]

The problem of computing a connected network with minimum interference is a fundamental problem in wireless sensor networks. Several models of interference have been studied in the literature. The most common one is the receiver-centric, in which the interference of a node p is defined as the number of other nodes whose transmission range covers p. In this paper, we study the problem of assigning a transmission range to each sensor, such that the resulting network is strongly connected and the total interference of the network is minimized. For the one-dimensional case, we show how to solve the problem optimally in O (n 3) time. For the two-dimensional case, we show that the problem is NP-complete and give a polynomial-time 2-approximation algorithm for the problem. [ABSTRACT FROM AUTHOR]

Consider n identical relocatable sensors , with sensing range r and visibility range 2 r , initially placed at arbitrary positions on a line segment barrier; each sensor can detect the presence of an intruder in its sensing range, and is said to cover the portion of the barrier that intersects with its sensing range. Sensors operate in Look-Compute-Move cycles: in a cycle a sensor determines the positions of sensors in its visibility range, it computes its next position (within its visibility range), and then moves to the calculated position. The barrier coverage problem we consider is for the sensors to independently make decisions and movements so to reach final positions whereby they collectively cover the barrier; in particular we are interested in oblivious (or memoryless) sensors, and focus on the impact that the level of synchrony and the presence/absence of orientation (i.e., global notion of "left-right") have on the solvability of the problem. It is known that without orientation, oblivious sensors can solve the problem if they are fully synchronous (i.e., they operate in synchronous rounds and are all active at every round). In this paper, we prove that orientation is critical to being able to solve the problem if we relax the assumption of full synchronization. We first show that if sensors are unoriented, then barrier coverage is unsolvable even in the semi-synchronous setting. In contrast, if sensors agree on a global orientation, then we give an algorithm for barrier coverage, even in the completely asynchronous setting. Finally, we extend the existing result of Cohen and Peleg and show that convergence to barrier coverage by unoriented sensors in the semi-synchronous model is possible with bounded visibility range 2 r + ρ (for arbitrarily small ρ > 0) and bounded mobility range r. [ABSTRACT FROM AUTHOR]

The Minimum Vertex Cover P roblem is the optimization problem of finding a vertex cover V c of minimal cardinality in a given graph. It is a classic NP-hard problem, and various algorithms have been suggested for it. In this paper, we start with a basic algorithm for solving the problem. Using a probabilistic idea, we use it to develop an improved algorithm. The algorithm is greedy; at each step it adds to the cover a vertex such that the expected cover size, if we continue randomly after this step, is minimal. We study the new algorithm theoretically and empirically, and run simulations to compare its performance to that of some algorithms of a similar nature. [ABSTRACT FROM AUTHOR]

This paper investigates the problem of Byzantine Agreement in a synchronous system where malicious agents can move from process to process, corrupting their host. Earlier works on the problem are based on biased models which, as we argue in the paper, give an unfair advantage either to the correct processes or to the adversary controlling the malicious agents. Indeed, earlier studies of the problem assume that, after a malicious agent has left a process, that process, said to be cured, is able to instantly and accurately detect the fact that it was corrupted in earlier rounds, and thus can take local actions to recover a valid state (Garay's model). We found no justification for that assumption which clearly favors correct processes. Under that model, an algorithm is known for n > 4 t , where n is the number of processes and t the maximum number of malicious agents. The tightness of the bound is however unknown. In contrast, more recent works on the problem remove the assumption on detection and assume instead that a malicious agent may have left corrupted messages in the send queue of a cured process in addition to a corrupted state. As a result, the adversary controlling the malicious agents can corrupt the messages sent by cured processes, in addition to those sent by the newly corrupted ones, thus doubling the number of effective faults. Under that model, which favors the malicious agents, the problem can be solved if and only if n > 6 t . In this paper, we refine the latter model to avoid the above biases. While a cured process may send messages (based on a state corrupted by the malicious agent), it will behave correctly in the way it sends those messages: i.e., send messages according to the algorithm. Surprisingly, in this model we could derive a new non-trivial tight bound for Byzantine Agreement. We prove that at least 5 t + 1 processors are needed in order to tolerate t mobile Byzantine agents and provide a time optimal algorithm that matches this lower bound, altogether with a formal specification of the problem. [ABSTRACT FROM AUTHOR]

Abstract We study, in this paper, a taxi-sharing problem, called Dial-a-Ride problem with money as an incentive (DARP-M). This problem consists in defining a set of taxis that will be shared by different clients in order to reduce their bill by a given factor α < 1. To achieve this, each client shares the cost of the ride with other passengers. More precisely, the fragments of the ride in which the client is alone is fully paid by this client and, for each fragment in which the client shares the taxi with other passengers, the cost is equally divided between the passengers. In addition to this cost constraint, the taxi must satisfy a time window constraint for each passenger and a capacity constraint. We define three versions of the problem: max-DARP-M where the objective is to drive the maximum number of clients with an arbitrarily large number of taxis; max-1-DARP-M in which we want to drive the maximum number of clients with one taxi; and 1-DARP-M which consists in deciding whether it is possible to drive at least one client while satisfying the constraints. We study the parameterized complexity and approximability of those problems with respect to four parameters: the factor α , the capacity c a p a of the taxis, the maximum size TW of the time windows of the clients, and the value S of an optimal solution. Among other results, we prove that 1-DARP-M is NP-Complete and max-DARP-M and max-1-DARP-M cannot be approximated in polynomial time to within any variable ratio even if α , c a p a and TW are fixed and if the road network is a planar graph. We also give a polynomial algorithm for max-1-DARP-M for the case where c a p a and TW are fixed and where the network does not contain a circuit. This algorithm implies a 1 n -polynomial approximation for max-DARP-M. [ABSTRACT FROM AUTHOR]

Abstract This paper proposes an exact exponential algorithm for the single machine total tardiness problem. It exploits the structure of a basic branch-and-reduce framework based on the well known Lawler's decomposition property that solves the problem with worst-case complexity in time O ⁎ (3 n) and polynomial space. The proposed algorithm, called branch-and-merge, is an improvement of the branch-and-reduce technique with the embedding of a node merging operation. Its time complexity converges to O ⁎ (2 n) keeping the space complexity polynomial. This improves upon the best-known complexity result for this problem provided by dynamic programming across the subsets with O ⁎ (2 n) worst-case time and space complexity. The branch-and-merge technique is likely to be generalized to other sequencing problems with similar decomposition properties. [ABSTRACT FROM AUTHOR]

A 2-club is a graph of diameter at most two. In the decision version of the 2-Club Cluster Edge Deletion problem, an undirected graph G is given along with an integer k≥0 as parameter, and the question is whether G can be transformed into a disjoint union of 2-clubs by deleting at most k edges. A simple fixed-parameter algorithm solves the problem in O ⁎ (3 k) , and a decade-old algorithm improved this running to O ⁎ (2.74 k) time via a more sophisticated case analysis. Unfortunately, this latter algorithm is shown to have a flawed branching scenario. A fixed-parameter algorithm that breaks the 3 k barrier is presented in this paper, with a running time in O ⁎ (2.692 k). This also improves the previously claimed running time. [ABSTRACT FROM AUTHOR]

A simple Voting algorithm has been shown to be effective at solving the OneMax problem in the presence of high levels of posterior noise in our previous research. In this paper, we extend this analysis to several different noise models, and show that the Voting algorithm remains robust in all of them. We consider the prior noise model and the partial evaluation of randomly selected bits. The Voting algorithm has superior runtime bounds on these problems compared to other published algorithms. We also introduce a new variant of partial evaluation, and further consider the simple model when a comparison-based oracle produces incorrect results with a fixed probability. [ABSTRACT FROM AUTHOR]

Graph editing problems offer an interesting perspective on sub- and supergraph identification problems for a large variety of target properties. They have also attracted significant attention in recent years, particularly in the area of parameterized complexity as the problems have rich parameter ecologies. In this paper we examine generalisations of the notion of editing a graph to obtain a regular subgraph. In particular we extend the notion of regularity to include two variants of edge-regularity along with the unifying constraint of strong regularity. We present a number of results, with the central observation that these problems retain the general complexity profile of their regularity-based inspiration: when the number of edits k and the maximum degree r are taken together as a combined parameter, the problems are tractable (i.e. in FPT ), but are otherwise intractable. We also examine variants of the basic editing to obtain a regular subgraph problem from the perspective of parameterizing by the treewidth of the input graph. In this case the treewidth of the input graph essentially becomes a limiting parameter on the natural k + r parameterization. [ABSTRACT FROM AUTHOR]

This paper presents a new Electromagnetism-like Mechanism (EM) algorithm with Split, Probe and Compare feature (SPC-EM). The proposed algorithm replaces the local search segment of a standard EM with a new search scheme named Split, Probe, and Compare (SPC). A nonlinear equation is designed to systematically and dynamically adjust the length of the probes based on the outcome of the Compare segment in each iteration. Extensive computational simulations and comparisons on 10 different benchmark problems from the literature were carried out. Results show that the new modified mechanism outperformed all other algorithms involved in the benchmarking. We thus conclude that the proposed SPC-EM works well with the designed probe-length tuning equation in solving numerical optimization problems. [ABSTRACT FROM AUTHOR]

In the Possible winner problem in computational social choice theory, we are given a set of partial preferences and the question is whether a distinguished candidate could be made winner by extending the partial preferences to linear preferences. Previous work has provided, for many common voting rules, fixed parameter tractable algorithms for the Possible winner problem, with number of candidates as the parameter. However, the corresponding kernelization question is still open and in fact, has been mentioned as a key research challenge [10] . In this paper, we settle this open question for many common voting rules. We show that the Possible winner problem for maximin, Copeland, Bucklin, ranked pairs, and a class of scoring rules that includes the Borda voting rule does not admit a polynomial kernel with the number of candidates as the parameter. We show however that the Coalitional manipulation problem which is an important special case of the Possible winner problem does admit a polynomial kernel for maximin, Copeland, ranked pairs, and a class of scoring rules that includes the Borda voting rule, when the number of manipulators is polynomial in the number of candidates. A significant conclusion of our work is that the Possible winner problem is harder than the Coalitional manipulation problem since the Coalitional manipulation problem admits a polynomial kernel whereas the Possible winner problem does not admit a polynomial kernel. [ABSTRACT FROM AUTHOR]

We study the Multicut on Trees and the Generalized Multiway Cut on Trees problems. For the Multicut on Trees problem, we present a parameterized algorithm that runs in time O ⁎ ( ρ k ) , where ρ = 2 + 1 < 1.554 is the positive root of the polynomial x 4 − 2 x 2 − 1 . This improves the current-best algorithm of Chen et al. that runs in time O ⁎ ( 1.619 k ) . For the Generalized Multiway Cut on Trees problem, we show that this problem is solvable in polynomial time if the number of terminal sets is fixed; this answers an open question posed in a recent paper by Liu and Zhang. By reducing the Generalized Multiway Cut on Trees problem to the Multicut on Trees problem, our results give a parameterized algorithm that solves the Generalized Multiway Cut on Trees problem in time O ⁎ ( ρ k ) . [ABSTRACT FROM AUTHOR]

In this paper we study the problem of partitioning a convex polygon P of n vertices into m polygons of equal area and perimeter. We give an algorithm for m = 2 that runs in O ( n ) time, and an algorithm for m = 2 k , where k is an integer, that runs in O ( ( 2 n ) k ) time. These are the first algorithms to solve this problem. [ABSTRACT FROM AUTHOR]

This paper studies two problems of locating two paths in a tree with positive and negative weights. The first problem has objective to minimize the sum of minimum weighted distances from every vertex of the tree to the two paths, while the second is to minimize the sum of the weighted minimum distances from every vertex of the tree to the two paths. We develop an O ( n 2 ) algorithm based on the optimal properties for the first problem, and also an O ( n 3 ) algorithm for the second problem. [ABSTRACT FROM AUTHOR]

A plane graph is a planar graph with a fixed planar embedding. In this paper we define a special spanning tree of a plane graph which we call a good spanning tree. Not every plane graph has a good spanning tree. We show that every connected planar graph has a planar embedding with a good spanning tree. Using a good spanning tree, we show that every connected planar graph G of n vertices has a straight-line monotone grid drawing on an O ( n ) × O ( n 2 ) grid, and such a drawing can be found in O ( n ) time. Our results solve two open problems on monotone drawings of planar graphs posed by Angelini et al. Using good spanning trees, we also give simple linear-time algorithms for finding a 2-visibility representation of a connected planar graph G of n vertices on a ( 2 n − 1 ) × ( 2 n − 1 ) grid and for finding a spike- VPG representation of G on a ( 2 n − 1 ) × n grid. [ABSTRACT FROM AUTHOR]

The Closest String problem asks to find a string s which is not too far from each string in a set of m input strings, where the distance is taken as the Hamming distance. This well-studied problem has various applications in computational biology and drug design. In this paper, we introduce a new variant of Closest String where the input strings can contain wildcards that can match any letter in the alphabet, and the goal is to find a solution string without wildcards. We call this problem the Closest String with Wildcards problem, and we analyze it in the framework of parameterized complexity. Our study determines for each natural parameterization whether this parameterization yields a fixed-parameter algorithm, or whether such an algorithm is highly unlikely to exist. [ABSTRACT FROM AUTHOR]

We consider the problem of finding k centers for n weighted points on a real line. This (weighted) k -center problem was solved in O ( n log ⁡ n ) time previously by using Cole's parametric search and other complicated approaches. In this paper, we present an easier O ( n log ⁡ n ) time algorithm that avoids the parametric search, and in certain special cases our algorithm solves the problem in O ( n ) time. In addition, our techniques involve developing interesting data structures for processing queries that find a lowest point in the common intersection of a certain subset of half-planes. This subproblem is interesting in its own right and our solution for it may find other applications as well. [ABSTRACT FROM AUTHOR]

Given a graph G = ( V , E ) with a positive weight function w on the vertices of G , a global powerful alliance of G is a subset S of V such that for every vertex v at least half of the total weight in the closed neighborhood of v is contributed by the vertices of S . A global offensive alliance is a subset S of V such that the above condition holds for every vertex v not in S . Finding the smallest such set in general graphs is NP-complete for both of these problems, even when the weights are all the same. In this paper, we give linear time algorithms that find the smallest global offensive and global powerful alliance of any weighted tree T = ( V , E ) . [ABSTRACT FROM AUTHOR]

In this paper, we revisit the much studied problem of Pattern Matching with Swaps (Swap Matching problem, for short). We first present a graph-theoretic model, which opens a new and so far unexplored avenue to solve the problem. Then, using the model, we devise two efficient algorithms to solve the swap matching problem. The resulting algorithms are adaptations of the classic shift-and algorithm. For patterns having length similar to the word-size of the target machine, both the algorithms run in linear time considering a fixed alphabet. [ABSTRACT FROM AUTHOR]

This is a corrigendum for our paper [1] , as we have found that the first FPT algorithm for the Maximum-Duo Preservation String Mapping Problem we presented is incorrect. However, we show that, by slightly modifying the color-coding technique on which the algorithm is based, we can fix the error, thus giving a correct FPT algorithm for Maximum-Duo Preservation String Mapping Problem. [ABSTRACT FROM AUTHOR]