{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:00:29Z","timestamp":1760241629072,"version":"build-2065373602"},"reference-count":32,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2018,6,28]],"date-time":"2018-06-28T00:00:00Z","timestamp":1530144000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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=\u0398(log|V|). MCV and MCD run in polynomial time ifk=O((log|V|)\u03b1), where \u03b1&lt;1. If k=\u0398((log|V|)1+\u03f5), for \u03f5&gt;0, then MIS, MVC and MDS run in quasi-polynomial time. If k=\u0398(log|V|), then MCV and MCD run in quasi-polynomial time.<\/jats:p>","DOI":"10.3390\/a11070093","type":"journal-article","created":{"date-parts":[[2018,6,28]],"date-time":"2018-06-28T10:53:33Z","timestamp":1530183213000},"page":"93","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Layered Graphs: Applications and Algorithms"],"prefix":"10.3390","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8768-9183","authenticated-orcid":false,"given":"Bhadrachalam","family":"Chitturi","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, Amrita Vishwa Vidyapeetham, Amritapuri 690525, India"},{"name":"Department of Computer Science, University of Texas at Dallas, Richardson, TX 75083, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1474-3695","authenticated-orcid":false,"given":"Srijith","family":"Balachander","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Amrita Vishwa Vidyapeetham, Amritapuri 690525, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7972-1382","authenticated-orcid":false,"given":"Sandeep","family":"Satheesh","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Amrita Vishwa Vidyapeetham, Amritapuri 690525, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2736-0420","authenticated-orcid":false,"given":"Krithic","family":"Puthiyoppil","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Amrita Vishwa Vidyapeetham, Amritapuri 690525, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,6,28]]},"reference":[{"key":"ref_1","unstructured":"Chitturi, B., Sudborough, H., Voit, W., and Feng, X. (2008, January 27\u201329). Adjacent Swaps on Strings. Proceedings of the Computing and Combinatorics (COCOON 2008), Dalian, China."},{"key":"ref_2","unstructured":"Chitturi, B., Mohandas, M., Sudborough, H., and Voit, W. (2018). Adjacent Swaps on Strings. Algorithms Mol. Biol., submitted."},{"key":"ref_3","unstructured":"Alberts, B., Johnson, A., Lewis, J., Raff, M., Roberts, K., and Walter, P. (2002). Molecular Biology of the Cell, Garland Science."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Feng, X., Chitturi, B., and Sudborough, H. (2010). Sorting circular permutations by bounded transpositions. Advances in Computational Biology, Springer.","DOI":"10.1007\/978-1-4419-5913-3_81"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Karp, R.M. (1972). Reducibility among combinatorial problems. Complexity of Computer Computations, Springer.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"ref_6","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Harary, F. (1969). Graph Theory, Addison-Wesley Pub. Co.","DOI":"10.21236\/AD0705364"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1137\/0201013","article-title":"Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum vertex cover of a chordal graph","volume":"1","author":"Gavril","year":"1972","journal-title":"SIAM J. Comput."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1002\/net.3230030305","article-title":"Algorithms for a maximum clique and a maximum independent set of a circle graph","volume":"3","author":"Gavril","year":"1973","journal-title":"Networks"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/BF02253207","article-title":"The complexity of comparability graph recognition and coloring","volume":"18","author":"Golumbic","year":"1977","journal-title":"Computing"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1016\/0095-8956(80)90074-X","article-title":"On maximal independent sets of vertices in claw-free graphs","volume":"28","author":"Minty","year":"1980","journal-title":"J. Comb. Theory Ser. B"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1002\/net.3230120410","article-title":"Efficient algorithms for interval graphs and circular arc graphs","volume":"12","author":"Gupta","year":"1982","journal-title":"Networks"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1007\/BF01934098","article-title":"An optimal time algorithm for finding a maximum weight independent set in a tree","volume":"28","author":"Chen","year":"1988","journal-title":"BIT Numer. Math."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0020-0190(92)90216-I","article-title":"An efficient algorithm for finding a maximum weight 2-independent set on interval graphs","volume":"43","author":"Hsiao","year":"1992","journal-title":"Inf. Process. Lett."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"537","DOI":"10.1137\/0206038","article-title":"Finding a maximum independent set","volume":"6","author":"Tarjan","year":"1977","journal-title":"SIAM J. Comput."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0196-6774(86)90032-5","article-title":"Algorithms for maximum independent sets","volume":"7","author":"Robson","year":"1986","journal-title":"J. Algorithms"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"269","DOI":"10.7155\/jgaa.00207","article-title":"On the Maximum Independent Set Problem in Subclasses of Planar Graphs","volume":"14","author":"Lozin","year":"2010","journal-title":"J. Graph Algorithms Appl."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"826","DOI":"10.1137\/0132071","article-title":"The rectilinear Steiner tree problem is NP-complete","volume":"32","author":"Garey","year":"1977","journal-title":"SIAM J. Appl. Math."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Bondy, J.A., and Murty, U.S.R. (1976). Graph Theory with Application, Macmillan.","DOI":"10.1007\/978-1-349-03521-2"},{"key":"ref_20","first-page":"116","article-title":"Graphen und matrizen","volume":"38","author":"Konig","year":"1931","journal-title":"Mat. Fiz. Lapok"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/j.amc.2016.12.004","article-title":"Complexity and algorithms for the connected vertex cover problem in 4-regular graphs","volume":"301","author":"Li","year":"2017","journal-title":"Appl. Math. Comput."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1145\/322326.322328","article-title":"Linear-time computability of combinatorial problems on series-parallel graphs","volume":"29","author":"Takamizawa","year":"1982","journal-title":"J. ACM"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0020-0190(84)90126-1","article-title":"Dominating sets for split and bipartite graphs","volume":"19","author":"Bertossi","year":"1984","journal-title":"Inf. Process. Lett."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/0020-0190(75)90011-3","article-title":"A linear algorithm for the domination number of a tree","volume":"4","author":"Cockayne","year":"1975","journal-title":"Inf. Process. Lett."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/174644.174650","article-title":"Approximation algorithms for NP-complete problems on planar graphs","volume":"41","author":"Baker","year":"1994","journal-title":"J. ACM"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/0304-3975(87)90067-3","article-title":"The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs","volume":"53","year":"1987","journal-title":"Theor. Comput. Sci."},{"key":"ref_27","unstructured":"Hung, R.W., Chang, M.S., and Ming-Hsiung, C. (2002, January 29\u201330). A linear algorithm for the connected domination problem on circular-arc graphs. Proceedings of the 19th Workshop on Combinatorial Mathematics and Computation Theory, Kaohsiung, Taiwan."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/s00453-007-9145-z","article-title":"Solving connected dominating set faster than 2n","volume":"52","author":"Fomin","year":"2008","journal-title":"Algorithmica"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1007\/s10107-009-0297-2","article-title":"Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs","volume":"128","author":"Gouveia","year":"2011","journal-title":"Math. Program."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1142\/S1793830911001206","article-title":"A note on complexity of genetic mutations. Discrete Mathematics","volume":"3","author":"Chitturi","year":"2011","journal-title":"Discret. Math. Algorithms Appl."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Chitturi, B., Bein, D., and Grishin, N. (2010, January 15\u201317). Complete enumeration of compact structural motifs in proteins. Proceedings of the International Symposium on Biocomputing, Kerala, India.","DOI":"10.1145\/1722024.1722047"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"4392","DOI":"10.1016\/j.jmb.2016.07.022","article-title":"Compact Structure Patterns in Proteins","volume":"428","author":"Chitturi","year":"2016","journal-title":"J. Mol. Biol."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/7\/93\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:10:37Z","timestamp":1760195437000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/7\/93"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,28]]},"references-count":32,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2018,7]]}},"alternative-id":["a11070093"],"URL":"https:\/\/doi.org\/10.3390\/a11070093","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2018,6,28]]}}}