{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,8]],"date-time":"2025-05-08T04:09:56Z","timestamp":1746677396296,"version":"3.40.5"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,5,7]],"date-time":"2025-05-07T00:00:00Z","timestamp":1746576000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,5,7]],"date-time":"2025-05-07T00:00:00Z","timestamp":1746576000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Matej Bel University in Bansk\u00e1 Bystrica"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discov Computing"],"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>In traffic management and urban planning, it is necessary to allocate time slots for the free flow of traffic on intersected roads so that no traffic is allowed to course on any two adjacent roads simultaneously, therefore avoiding collisions of vehicles on said intersections. This NP-complete problem can be modelled and solved via edge coloring of a graph representing a selected intersection system, where the number of needed time slots is equal to the number of colors required for conflict-free edge coloring of such a graph \u2212 a property called chromatic index of a graph. The work presented in the scope of this study focuses on the design and implementation of an anomaly detection process for the identification of the chromatic index of a selected subset of intersections represented by a cubic graph, where conventionally three colors suffice for proper coloring, but in rare (anomalous) cases four are needed. The main objective of the study is achieving lower computational requirements when compared to standard graph edge coloring. Eight approaches to the anomaly detection \u2212 isolation forest, one-class random forest, multilayer perceptron network, support vector machine, encoder, and three types of ensemble models \u2212 were applied to the selected problem and evaluated from the point of view of decision-making quality and the duration of computation. Based on the reached results, the simple model of a one class random forest and the ensemble model consisting of one class random forest, multilayer perceptron network, and support vector machine applying AND voting system, are the most fitting of the considered approaches with 97% and 99% respective recall values in anomaly identification. Both approaches also reach better time complexity of training and testing than standard edge-coloring methods of chromatic index identification.<\/jats:p>","DOI":"10.1007\/s10791-025-09579-1","type":"journal-article","created":{"date-parts":[[2025,5,7]],"date-time":"2025-05-07T13:02:55Z","timestamp":1746622975000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Avoiding vehicle collisions in intersections using anomaly detection for the identification of chromatic index value in cubic graphs"],"prefix":"10.1007","volume":"28","author":[{"given":"Bianka","family":"Modrovi\u010dov\u00e1","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adam","family":"Dud\u00e1\u0161","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,5,7]]},"reference":[{"key":"9579_CR1","doi-asserted-by":"publisher","unstructured":"Huang XH, et al. Multi-attention gated temporal graph convolution neural network for traffic flow forecasting. Cluster Comput. 2024. https:\/\/doi.org\/10.1007\/s10586-024-04652-8.","DOI":"10.1007\/s10586-024-04652-8"},{"key":"9579_CR2","doi-asserted-by":"publisher","unstructured":"Mulas R. Maximal Colourings for Graphs. Graphs Combin. 2024. https:\/\/doi.org\/10.1007\/s00373-024-02823-3.","DOI":"10.1007\/s00373-024-02823-3"},{"key":"9579_CR3","doi-asserted-by":"publisher","unstructured":"Gy\u00e1rf\u00e1s A, et al. Proper edge colorings of planar graphs with rainbow $$\\text{C}_4$$-s. J Graph Theory. 2024. https:\/\/doi.org\/10.1002\/jgt.23163.","DOI":"10.1002\/jgt.23163"},{"key":"9579_CR4","doi-asserted-by":"publisher","unstructured":"Accurso C, et al. Weak dynamic coloring of planar graphs. Graphs Combin. 2024. https:\/\/doi.org\/10.1007\/s00373-023-02748-3.","DOI":"10.1007\/s00373-023-02748-3"},{"key":"9579_CR5","doi-asserted-by":"publisher","unstructured":"Shai O. Transforming engineering problems through graph representations. Adv Eng Inf. 2003. https:\/\/doi.org\/10.1016\/j.aei.2003.09.001.","DOI":"10.1016\/j.aei.2003.09.001"},{"key":"9579_CR6","unstructured":"Vizing VG. On an estimate of the chromatic class of a p-graph. Analiz: Diskret; 1964."},{"key":"9579_CR7","doi-asserted-by":"publisher","unstructured":"Dud\u00e1\u0161 A, Modrovi\u010dov\u00e1 B. Interpretable random forest model for identification of edge 3-uncolorable cubic graphs. Kybernetika, 2023. https:\/\/doi.org\/10.14736\/kyb-2023-6-0807","DOI":"10.14736\/kyb-2023-6-0807"},{"key":"9579_CR8","doi-asserted-by":"publisher","unstructured":"Beigel R, Eppstein D. 3-coloring in time O(1.3289n). Journal of Algorithms, 2005. https:\/\/doi.org\/10.5555\/1061279.1712328","DOI":"10.5555\/1061279.1712328"},{"key":"9579_CR9","doi-asserted-by":"publisher","unstructured":"Kowalik L. Improved edge-coloring with three colors. Theoretical Computer Science. 2009. https:\/\/doi.org\/10.1016\/j.tcs.2009.05.005.","DOI":"10.1016\/j.tcs.2009.05.005"},{"key":"9579_CR10","doi-asserted-by":"publisher","unstructured":"Dud\u00e1\u0161 A, Modrovi\u010dov\u00e1 B. Decision Trees in Proper Edge k-coloring of Cubic Graphs. 33rd Conference of Open Innovations Association FRUCT, 2023. https:\/\/doi.org\/10.23919\/FRUCT58615.2023.10143001","DOI":"10.23919\/FRUCT58615.2023.10143001"},{"key":"9579_CR11","doi-asserted-by":"crossref","unstructured":"Dud\u00e1\u0161 A, Modrovi\u010dov\u00e1 B. Determining chromatic index of cubic graph with the use of explainable classifiers: a comparative study. Journal of the Applied Mathematics, Statistics and Informatics, 2024. $$in\\ print$$","DOI":"10.2478\/jamsi-2024-0006"},{"key":"9579_CR12","doi-asserted-by":"publisher","unstructured":"de Silva PZ, et al. Interference graph dataset for machine learning-based register allocation. IEEE Access. 2024. https:\/\/doi.org\/10.1109\/ACCESS.2024.3481358.","DOI":"10.1109\/ACCESS.2024.3481358"},{"key":"9579_CR13","doi-asserted-by":"publisher","unstructured":"Ahmad OU, et al. A graph machine learning framework to compute zero forcing sets in graphs. IEEE Transactions on Network Science and Engineering. 2024. https:\/\/doi.org\/10.1109\/TNSE.2023.3337750.","DOI":"10.1109\/TNSE.2023.3337750"},{"key":"9579_CR14","doi-asserted-by":"publisher","DOI":"10.1016\/j.neunet.2025.107169","author":"X Wang","year":"2025","unstructured":"Wang X, et al. Graph anomaly detection based on hybrid node representation learning. Neural Netw. 2025. https:\/\/doi.org\/10.1016\/j.neunet.2025.107169.","journal-title":"Neural Netw"},{"key":"9579_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-014-0365-y","author":"L Akoglu","year":"2015","unstructured":"Akoglu L, et al. Graph based anomaly detection and description: a survey. Data Mining Knowl Discov. 2015. https:\/\/doi.org\/10.1007\/s10618-014-0365-y.","journal-title":"Data Mining Knowl Discov"},{"key":"9579_CR16","doi-asserted-by":"publisher","DOI":"10.1080\/12265934.2022.2102538","author":"TW Sanchez","year":"2023","unstructured":"Sanchez TW, et al. The prospects of artificial intelligence in urban planning. Int J Urban Sci. 2023. https:\/\/doi.org\/10.1080\/12265934.2022.2102538.","journal-title":"Int J Urban Sci"},{"key":"9579_CR17","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2024.107525","author":"H Liu","year":"2025","unstructured":"Liu H, et al. Bus travel feature inference with small samples based on multi-clustering topic model over internet of things. Fut Gen Comput Syst. 2025. https:\/\/doi.org\/10.1016\/j.future.2024.107525.","journal-title":"Fut Gen Comput Syst"},{"key":"9579_CR18","doi-asserted-by":"publisher","DOI":"10.1080\/19439962.2024.2320630","author":"SM Haroon","year":"2024","unstructured":"Haroon SM, Ryan A. Understanding key factors in automated vehicle collisions: automating data extraction and analyzing key insights using explainable AI. J Tran Safety Sec. 2024. https:\/\/doi.org\/10.1080\/19439962.2024.2320630.","journal-title":"J Tran Safety Sec"},{"key":"9579_CR19","doi-asserted-by":"publisher","DOI":"10.1038\/s41598-022-27026-9","author":"AHM Muzahid","year":"2023","unstructured":"Muzahid AHM, et al. Multiple vehicle cooperation and collision avoidance in automated vehicles: survey and an AI-enabled conceptual framework. Sci Rep. 2023. https:\/\/doi.org\/10.1038\/s41598-022-27026-9.","journal-title":"Sci Rep"},{"key":"9579_CR20","doi-asserted-by":"publisher","unstructured":"Bansal N, Pahuja S. A Generic Review on Anomaly Detection. Proceedings of 3rd International Conference on Machine Learning, Advances in Computing, Renewable Energy and Communication. Lect Note Elect Eng, 2022. https:\/\/doi.org\/10.1007\/978-981-19-2828-4_45","DOI":"10.1007\/978-981-19-2828-4_45"},{"key":"9579_CR21","doi-asserted-by":"publisher","unstructured":"Chavan VD, Yalagi PS. Review of Machine Learning Tools and Techniques for Anomaly Detection. ICT for Intelligent Systems. 2023. https:\/\/doi.org\/10.1007\/978-981-99-3982-4_34.","DOI":"10.1007\/978-981-99-3982-4_34"},{"key":"9579_CR22","doi-asserted-by":"publisher","DOI":"10.1145\/3609333","author":"Z Li","year":"2024","unstructured":"Li Z, et al. A survey on explainable anomaly detection. ACM Trans Knowl Discov Data. 2024. https:\/\/doi.org\/10.1145\/3609333.","journal-title":"ACM Trans Knowl Discov Data"},{"key":"9579_CR23","doi-asserted-by":"publisher","DOI":"10.1186\/s40537-020-00320-x","author":"S Thudumu","year":"2020","unstructured":"Thudumu S, et al. A comprehensive survey of anomaly detection techniques for high dimensional big data. J Big Data. 2020. https:\/\/doi.org\/10.1186\/s40537-020-00320-x.","journal-title":"J Big Data"},{"key":"9579_CR24","doi-asserted-by":"publisher","unstructured":"Fei TL, et al. 2012. Isolation-Based Anomaly Detection. ACM Trans Knowl Discov Data. 2012. https:\/\/doi.org\/10.1145\/2133360.2133363.","DOI":"10.1145\/2133360.2133363"},{"key":"9579_CR25","doi-asserted-by":"publisher","unstructured":"D\u00e9sir C, et al. A new random forest method for one-class classification. Lect Note Comput Sci. 2012. https:\/\/doi.org\/10.1007\/978-3-642-34166-3_31.","DOI":"10.1007\/978-3-642-34166-3_31"},{"key":"9579_CR26","doi-asserted-by":"publisher","unstructured":"Tian S, et al. Anomaly detection using support vector machines. Lect Note Comput Sci. 2004. https:\/\/doi.org\/10.1007\/978-3-540-28647-9_97.","DOI":"10.1007\/978-3-540-28647-9_97"},{"key":"9579_CR27","doi-asserted-by":"publisher","unstructured":"Li Z, et al. 3D Industrial anomaly detection via dual reconstruction network. Appl Intell. 2024. https:\/\/doi.org\/10.1007\/s10489-024-05700-x.","DOI":"10.1007\/s10489-024-05700-x"},{"key":"9579_CR28","doi-asserted-by":"publisher","unstructured":"Shiomoto K. Network intrusion detection system based on an adversarial auto-encoder with few labeled training samples. J Netw Syst Manage. 2023. https:\/\/doi.org\/10.1007\/s10922-022-09698-w.","DOI":"10.1007\/s10922-022-09698-w"},{"key":"9579_CR29","doi-asserted-by":"publisher","unstructured":"Askari A, et al. Injecting the score of the first-stage retriever as text improves BERT-based re-rankers. Discov Comput. 2024. https:\/\/doi.org\/10.1007\/s10791-024-09435-8.","DOI":"10.1007\/s10791-024-09435-8"},{"key":"9579_CR30","doi-asserted-by":"publisher","unstructured":"Yansong L, et al. Selective ensemble method for anomaly detection based on parallel learning. Sci Rep. 2024. https:\/\/doi.org\/10.1038\/s41598-024-51849-3.","DOI":"10.1038\/s41598-024-51849-3"},{"key":"9579_CR31","doi-asserted-by":"crossref","unstructured":"Modrovi\u010dov\u00e1 B, Dud\u00e1\u0161 A. Cubic graph property dataset for machine learning models. 2024 IEEE 17th International Scientific Conference on Informatics, 2024. $$in\\ print$$","DOI":"10.1109\/Informatics62280.2024.10900911"},{"key":"9579_CR32","doi-asserted-by":"publisher","unstructured":"Ma J, et al. Vehicle-drone collaborative distribution path planning based on neural architecture search under the influence of carbon emissions. Discov Comput. 2024. https:\/\/doi.org\/10.1007\/s10791-024-09469-y.","DOI":"10.1007\/s10791-024-09469-y"},{"key":"9579_CR33","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84628-970-5","volume-title":"Graph Theory","author":"A Bondy","year":"2008","unstructured":"Bondy A, Murty USR. Graph Theory. London: Springer; 2008. (ISBN: 978-1-84628-969-9)."},{"key":"9579_CR34","doi-asserted-by":"publisher","unstructured":"Li HM, Hu JL. Feature consistency learning for anomaly detection. IEEE Trans Instrument Measure. 2025. https:\/\/doi.org\/10.1109\/TIM.2024.3522399.","DOI":"10.1109\/TIM.2024.3522399"},{"key":"9579_CR35","doi-asserted-by":"publisher","unstructured":"Deng SZ et al. Positive and unlabeled learning on generating strategy for weakly anomaly detection. Signal Image Video Process, 2025. https:\/\/doi.org\/10.1007\/s11760-024-03797-8","DOI":"10.1007\/s11760-024-03797-8"},{"key":"9579_CR36","doi-asserted-by":"publisher","unstructured":"De Meulemeester H, et al. Explainable unsupervised anomaly detection for healthcare insurance data. BMC Med Inf Decis Making. 2025. https:\/\/doi.org\/10.1186\/s12911-024-02823-6.","DOI":"10.1186\/s12911-024-02823-6"},{"key":"9579_CR37","doi-asserted-by":"publisher","unstructured":"Fu Y, et al. Long-term evolutionary patterns matter: Self-supervised anomaly detection on dynamic graphs. Knowl-based Syst. 2025. https:\/\/doi.org\/10.1016\/j.knosys.2025.113049.","DOI":"10.1016\/j.knosys.2025.113049"}],"container-title":["Discover Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10791-025-09579-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10791-025-09579-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10791-025-09579-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,7]],"date-time":"2025-05-07T13:03:02Z","timestamp":1746622982000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10791-025-09579-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,7]]},"references-count":37,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,12]]}},"alternative-id":["9579"],"URL":"https:\/\/doi.org\/10.1007\/s10791-025-09579-1","relation":{},"ISSN":["2948-2992"],"issn-type":[{"value":"2948-2992","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,5,7]]},"assertion":[{"value":"21 November 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 April 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 May 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"There are no Conflict of interest in this work.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"69"}}