Sandeep Satheesh

Sandeep Satheesh

orcid

Research Focus & Metrics

Academic Career Length

9Years (2018-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
28 June 2018 in Algorithms
Verified
Journal Article
Open access
PDF file
BCBhadrachalam Chitturi
Bhadrachalam Chitturi
SBSrijith Balachander
Srijith Balachander
SSSandeep Satheesh
Sandeep Satheesh
KPKrithic Puthiyoppil
Krithic Puthiyoppil
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 k=Θ(log|V|). MCV and MCD run in polynomial time ifk=O((log|V|)α), where α<1. If k=Θ((log|V|)1+ϵ), for ϵ>0, then MIS, MVC and MDS run in quasi-polynomial time. If k=Θ(log|V|), then MCV and MCD run in quasi-polynomial time.

2 May 2018 in Preprints.org
Verified
Preprint
Open access
BCBhadrachalam Chitturi
Bhadrachalam Chitturi
SBSrijith Balachander
Srijith Balachander
SSSandeep Satheesh
Sandeep Satheesh
KPKrithic Puthiyoppil
Krithic Puthiyoppil
The independent set, IS, on a graph G = ( V , E ) is V * ⊆ V such that no two vertices in V * have an edge between them. The MIS problem on G seeks to identify an IS with maximum cardinality, i.e. MIS. V * ⊆ V is a vertex cover, i.e. VC of G = ( V , E ) if every e ∈ E is incident upon at least one vertex in V * . V * ⊆ V is dominating set, DS, of G = ( V , E ) if ∀ v ∈ V either v ∈ V * or ∃ u ∈ V * and ( u , v ) ∈ E . The MVC problem on G seeks to identify a vertex cover with minimum cardinality, i.e. MVC. Likewise, MCV seeks a connected vertex cover, i.e. VC which forms one component in G, with minimum cardinality, i.e. MCV. A connected DS, CDS, is a DS that forms a connected component in G. The problems MDS and MCD seek to identify a DS and a connected DS i.e. CDS respectively with minimum cardinalities. MIS, MVC, MDS, MCV and MCD on a general graph are known to be NP-complete. Polynomial time algorithms are known for bipartite graphs, chordal graphs, cycle graphs, comparability graphs, claw-free graphs, interval graphs and circular arc graphs for some of these problems. We introduce a novel graph class, layered graph, where each layer refers to a subgraph containing at most some k vertices. Inter layer edges are restricted to the vertices in adjacent layers. We show that if k = Θ ( log ∣ V ∣ ) then MIS, MVC and MDS can be computed in polynomial time and if k = O ( ( log ∣ V ∣ ) α ) , where α < 1 , then MCV and MCD can be computed in polynomial time. If k = Θ ( ( log ∣ V ∣ ) 1 + ϵ ) , for ϵ > 0 , then MIS, MVC and MDS require quasi-polynomial time. If k = Θ ( log ∣ V ∣ ) then MCV, MCD require quasi-polynomial time. Layered graphs do have constraints such as bipartiteness, planarity and acyclicity.