Layered Graphs: Applications and Algorithms

Algorithms

Bhadrachalam Chitturi¹  Krithic Puthiyoppil¹  Sandeep Satheesh¹  Srijith Balachander¹ 

[1] Department of Computer Science and Engineering, Amrita Vishwa Vidyapeetham, Amritapuri 690525, India;

关键词: NP-complete;    layered graph;    quasi-polynomial time;    dynamic programming;    independent set;    vertex cover;    dominating set;    string transformations;    social networks;   

DOI  :  10.3390/a11070093

来源: DOAJ

【 摘 要 】

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. The MIS, MVC and MDS are computed in polynomial time if k=Θ(log|V|). MCV and MCD are computed polynomial time if k=O((log|V|)α), where α<1. If k=Θ((log|V|)1+ϵ), for ϵ>0, then MIS, MVC and MDS are computed in quasi-polynomial time. If k=Θ(log|V|), then MCV and MCD are computed in quasi-polynomial time.

【 授权许可】

Unknown