The computation of distances between strings has applications in molecular biology, music theory and pattern recognition. One such measure, called short reversal distance, has applications in evolutionary distance computation. It has been shown that this problem can be reduced to the computation of a maximum independent set on the corresponding graph that is constructed from the given input strings. The constructed graphs primarily fall into a class that we call layered graphs. In a layered graph, each layer refers to a subgraph containing, at most, some k vertices. The inter-layer edges are restricted to the vertices in adjacent layers. We study the MIS, MVC, MDS, MCV and MCD problems on layered graphs where MIS computes the maximum independent set; MVC computes the minimum vertex cover; MDS computes the minimum dominating set; MCV computes the minimum connected vertex cover; and MCD computes the minimum connected dominating set. MIS, MVC and MDS run in polynomial time if . MCV and MCD run in polynomial time if, where . If , for , then MIS, MVC and MDS run in quasi-polynomial time. If , then MCV and MCD run in quasi-polynomial time.
Sorting permutations with various operations has applications in genetics and computer interconnection networks where an operation is specified by its generator set. A transposition tree is a spanning tree over n vertices . T denotes an operation in which each edge is a generator. A value assigned to a vertex is called a token or a marker. The markers on vertices u and v can be swapped only if the pair . The initial configuration consists of a bijection from the set of vertices to the set of markers . The goal is to sort the initial configuration of T, i.e., an input permutation, by applying the minimum number of swaps or moves in T. Computationally tractable optimal algorithms to sort permutations are known only for a few classes of transposition trees. We study a class of transposition trees called a broom and its variation a double broom. A single broom is a tree obtained by joining the centre vertex of a star with one of the two leaf vertices of a path graph. A double broom is an extension of a single broom where the centre vertex of a second star is connected to the terminal vertex of the path in a single broom. We propose a simple and efficient algorithm to obtain an optimal swap sequence to sort permutations with the transposition tree broom and a novel optimal algorithm to sort permutations with a double broom. We also introduce a new class of trees named millipede tree and prove that yields a tighter upper bound for sorting permutations with a balanced millipede tree compared to . Algorithms and are designed previously.