Layered Graphs: Applications and Algorithms

Simple item page
dc.contributor.ORCID0000-0002-8768-9183 (Chitturi, B)
dc.contributor.authorChitturi, Bhadrachalam
dc.contributor.authorBalachander, S.
dc.contributor.authorSatheesh, S.
dc.contributor.authorPuthiyoppil, K.
dc.contributor.utdAuthorChitturi, Bhadrachalam
dc.date.accessioned2019-07-25T22:30:29Z
dc.date.available2019-07-25T22:30:29Z
dc.date.created2018-06-28
dc.description.abstractThe 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 run in polynomial time if k=O((log |V|) ^α) where a < 1. If k = Θ((log |V|)^{1+e}), for e > 0, then MIS, MVC and MDS run in quasi-polynomial time. If k = Θ(log |V|), then MCV and MCD run in quasi-polynomial time.
dc.description.departmentErik Jonsson School of Engineering and Computer Science
dc.identifier.bibliographicCitationChitturi, B., S. Balachander, S. Satheesh, and K. Puthiyoppil. 2018. "Layered graphs: Applications and algorithms." Algorithms 11(7): art. 93, doi:10.3390/a11070093
dc.identifier.issn1999-4893
dc.identifier.issue7
dc.identifier.urihttps://hdl.handle.net/10735.1/6722
dc.identifier.volume11
dc.language.isoen
dc.publisherMDPI AG
dc.relation.urihttp://dx.doi.org/10.3390/a11070093
dc.rightsCC BY 4.0 (Attribution)
dc.rights©2018 The Authors
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/
dc.source.journalAlgorithms
dc.subjectDynamic programming
dc.subjectNP-complete problems
dc.subjectSocial networks
dc.subjectApproximation algorithms
dc.subjectEngineering—Graphic methods
dc.subjectMolecular biology
dc.subjectPattern perception
dc.subjectSet theory
dc.titleLayered Graphs: Applications and Algorithms
dc.title.alternativeAlgorithms
dc.type.genrearticle

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
JECS-2061-279824.37.pdf
Size:
557.89 KB
Format:
Adobe Portable Document Format
Description:
Article
Download

Collections

JECS Staff and Student Research