{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:44:43Z","timestamp":1760237083475,"version":"build-2065373602"},"reference-count":27,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2020,2,20]],"date-time":"2020-02-20T00:00:00Z","timestamp":1582156800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>The weighted independent set problem on     P 5    -free graphs has numerous applications, including data mining and dispatching in railways. The recognition of     P 5    -free graphs is executed in polynomial time. Many problems, such as chromatic number and dominating set, are NP-hard in the class of     P 5    -free graphs. The size of a minimum independent feedback vertex set that belongs to a     P 5    -free graph with n vertices can be computed in     O (  n 16  )     time. The unweighted problems, clique and clique cover, are NP-complete and the independent set is polynomial. In this work, the     P 5    -free graphs using the weak decomposition are characterized, as is the dominating clique, and they are given an     O ( n ( n + m ) )     recognition algorithm. Additionally, we calculate directly the clique number and the chromatic number; determine in     O ( n )     time, the size of a minimum independent feedback vertex set; and determine in     O ( n + m )     time the number of stability, the dominating number and the minimum clique cover.<\/jats:p>","DOI":"10.3390\/sym12020304","type":"journal-article","created":{"date-parts":[[2020,2,26]],"date-time":"2020-02-26T04:18:29Z","timestamp":1582690709000},"page":"304","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Recognition and Optimization Algorithms for P5-Free Graphs"],"prefix":"10.3390","volume":"12","author":[{"given":"Mihai","family":"Talmaciu","sequence":"first","affiliation":[{"name":"\u201cVasile Alecsandri\u201d University of Bacau, Calea Marasesti 157, 600115 Bacau, Romania"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7277-0747","authenticated-orcid":false,"given":"Lumini\u0163a","family":"Dumitriu","sequence":"additional","affiliation":[{"name":"\u201cDunarea de Jos\u201d University of Galati, Domneasca 47, 800008 Galati, Romania"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ioan","family":"\u015eu\u015fnea","sequence":"additional","affiliation":[{"name":"\u201cDunarea de Jos\u201d University of Galati, Domneasca 47, 800008 Galati, Romania"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Victor","family":"Lepin","sequence":"additional","affiliation":[{"name":"Institute of Mathematics of National Academy of Sciences of Belarus, Surganov 11, 220072 Minsk, Belarus"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6254-9291","authenticated-orcid":false,"given":"L\u00e1szl\u00f3 Barna","family":"Iantovics","sequence":"additional","affiliation":[{"name":"\u201cGeorge Emil Palade\u201d University of Medicine, Pharmacy, Sciences and Technology of Tg. Mures, Gh. Marinescu 38, 540139 Tg. Mures, Romania"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,2,20]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Zhao, S., and Xu, H. (2019). A Novel Preference Elicitation Technique Based on a Graph Model and Its Application to a Brownfield Redevelopment Conflict in China. Int. J. Environ. Res. Public Health, 16.","DOI":"10.3390\/ijerph16214088"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Eles, A., Halasz, L., Heckl, I., and Cabezas, H. (2019). Evaluation of the Energy Supply Options of a Manufacturing Plant by the Application of the P-Graph Framework. Energies, 12.","DOI":"10.3390\/en12081484"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Khan, K.U., Alam, A., Dolgorsuren, B., Uddin, M.A., Umair, M., Sang, U., Duong, V.T.T., Xu, W., and Lee, Y.K. (2017). LPaMI: A Graph-Based Lifestyle Pattern Mining Application Using Personal Image Collections in Smartphones. Appl. Sci., 7.","DOI":"10.3390\/app7121200"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Yin, K., Yu, L., and Li, X. (2017). An Improved Graph Model for Conflict Resolution Based on Option Prioritization and Its Application. Int. J. Environ. Res. Public Health, 14.","DOI":"10.3390\/ijerph14111311"},{"key":"ref_5","first-page":"313","article-title":"Recognition and combinatorial optimization algorithms for bipartite chain graphs","volume":"32","author":"Talmaciu","year":"2013","journal-title":"Comput. Inform."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Miller, A., Miron, D., and Maiya, S. (2018). GraphDraw\u2014A Tool for the Represention of Graphs Using Inherent Symmetry. Proceedings, 2.","DOI":"10.3390\/proceedings2010086"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Yun, U., Lee, G., and Kim, C.H. (2016). The Smallest Valid Extension-Based Efficient, Rare Graph Pattern Mining, Considering Length-Decreasing Support Constraints and Symmetry Characteristics of Graphs. Symmetry, 8.","DOI":"10.3390\/sym8050032"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1151","DOI":"10.3390\/sym7031151","article-title":"Multiple Minimum Support-Based Rare Graph Pattern Mining Considering Symmetry Feature-Based Growth Technique and the Differing Importance of Graph Elements","volume":"7","author":"Lee","year":"2015","journal-title":"Symmetry"},{"key":"ref_9","unstructured":"Berge, C. (1985). Graphs, Nort-Holland."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"159","DOI":"10.7151\/dmgt.1192","article-title":"Perfect connected-dominant graphs","volume":"23","author":"Zverovich","year":"2003","journal-title":"Discuss. Math. Graph Theory"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Vatshelle, M., and Villanger, Y. (2014). Independent Set in P5-Free Graphs in Polynomial Time, Society for Industrial and Applied Mathematics.","DOI":"10.1137\/1.9781611973402.43"},{"key":"ref_12","unstructured":"Flier, H., Mihalak, M., Schobel, A., Widmayer, P., and Zych, A. (2010, January 9). Vertex disjoint paths for dispatching in railways. Proceedings of the ATMOS, Liverpool, UK."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1145\/383891.383893","article-title":"Data mining with optimized two-dimensional association rules","volume":"26","author":"Fukuda","year":"2001","journal-title":"ACM Trans. Database Syst."},{"key":"ref_14","first-page":"1416","article-title":"Independent Feedback Vertex Set for P5-free Graphs","volume":"81","author":"Bonamy","year":"2018","journal-title":"Algorithmica"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1007\/s00453-008-9197-8","article-title":"Deciding k-colorability of P5-free graphs in polynomial time","volume":"57","author":"Lozin","year":"2010","journal-title":"Algorithmica"},{"key":"ref_16","first-page":"90","article-title":"On the complexity of determining the domination number in monogenic classes of graphs","volume":"2","author":"Korobitsyn","year":"1990","journal-title":"Diskret. Mat."},{"key":"ref_17","unstructured":"Kr\u00e1l, D., Kratochvil, J., Tuza, Z., and Woeginger, G.J. (2001, January 14\u201316). Complexity of coloring graphs without forbidden induced subgraphs. Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science, LNCS 2204, WG 2001, Boltenhagen, Germany."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/S0166-218X(03)00394-9","article-title":"P5-free augmenting graphs and the maximum stable set problem","volume":"132","author":"Gerber","year":"2004","journal-title":"Discret. Appl. Math."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/0012-365X(93)90539-6","article-title":"A decomposition for a class of {P5, P5}-free graphs","volume":"121","author":"Fouquet","year":"1993","journal-title":"Discret. Math."},{"key":"ref_20","unstructured":"Chudnovsky, M., Esperet, L., Lemoine, L., Maceli, P., Maffray, F., and Penev, I. (2019, November 03). Graphs with no induced P5 or P5. Available online: https:\/\/web.math.princeton.edu\/~mchudnov\/decompP4CP4.pdf."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0012-365X(93)E0111-G","article-title":"Dominating subgraphs in graphs with some forbidden structures","volume":"135","author":"Liu","year":"1994","journal-title":"Discret. Math."},{"key":"ref_22","unstructured":"Talmaciu, M. (2002). Decomposition Problems in the Graph Theory with Applications in Combinatorial Optimization. [Ph.D. Thesis, University \u201cAl. I. Cuza\u201d Iasi]."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"457","DOI":"10.15388\/Informatica.2007.188","article-title":"Recognition Algorithm for diamond-free graphs","volume":"18","author":"Talmaciu","year":"2007","journal-title":"Informatica"},{"key":"ref_24","unstructured":"Croitoru, C., Olaru, E., and Talmaciu, M. (2000, January 1\u20132). Confidentially connected graphs. Proceedings of the Annals of the University \u201cDunarea de Jos\u201d of Galati, International Conference \u201cThe Risk in Contemporany Economy\u201d, Galati, Romania."},{"key":"ref_25","unstructured":"Croitoru, C., and Talmaciu, M. (2000). On Confidentially Connected Graphs, Buletinul Siintific al Universitatii Baia Mare, Fascicola Matematica-Informatica. Seria B; Nr. 1."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0166-218X(90)90092-Q","article-title":"Difference Graphs","volume":"28","author":"Hammer","year":"1990","journal-title":"Discret. Appl. Math."},{"key":"ref_27","unstructured":"(2019, November 03). Information System on Graph Classes and Their Inclusions. Available online: http:\/\/www.graphclasses.org\/classes\/gc_396.html."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/12\/2\/304\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T08:59:32Z","timestamp":1760173172000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/12\/2\/304"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,20]]},"references-count":27,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2020,2]]}},"alternative-id":["sym12020304"],"URL":"https:\/\/doi.org\/10.3390\/sym12020304","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2020,2,20]]}}}