{"id":1237,"date":"2026-01-25T19:32:44","date_gmt":"2026-01-25T19:32:44","guid":{"rendered":"https:\/\/www.cs.ubbcluj.ro\/~meco\/a-pseudo-deterministic-noisy-extremal-optimization-algorithm-for-the-pairwise-connectivity-critical-node-detection-problem-2024\/"},"modified":"2026-02-01T12:07:41","modified_gmt":"2026-02-01T12:07:41","slug":"a-pseudo-deterministic-noisy-extremal-optimization-algorithm-for-the-pairwise-connectivity-critical-node-detection-problem-2024","status":"publish","type":"post","link":"https:\/\/www.cs.ubbcluj.ro\/~meco\/a-pseudo-deterministic-noisy-extremal-optimization-algorithm-for-the-pairwise-connectivity-critical-node-detection-problem-2024\/","title":{"rendered":"A Pseudo-Deterministic Noisy Extremal Optimization algorithm for the pairwise connectivity Critical Node Detection Problem (2024)"},"content":{"rendered":"<div class=\"entry-content\">\n<p>Logic Journal of the IGPL<\/p>\n<h2>Authors<\/h2>\n<p>No\u00e9mi Gask\u00f3, M. Suciu, R. Lung, Tam\u00e1s K\u00e9pes<\/p>\n<h2>Abstract<\/h2>\n<p>The critical node detection problem is a central task in computational graph theory due to its large applicability, consisting in deleting $k$ nodes to minimize a certain graph measure. In this article, we propose a new Extremal Optimization-based approach, the Pseudo-Deterministic Noisy Extremal Optimization (PDNEO) algorithm, to solve the Critical Node Detection variant in which the pairwise connectivity is minimized. PDNEO uses an adaptive pseudo-deterministic parameter to switch between random nodes and articulation points during the search, as well as other features, such as noise induction to preserve diversity, greedy search to better exploit the search space and a greater search space exploration mechanism. Numerical experiments on synthetic and real-world networks show the effectiveness of the proposed algorithm compared with existing methods.<\/p>\n<h2>Citation<\/h2>\n<pre class=\"wp-block-preformatted\">@Inproceedings{Gask\u00f32024APN,\n author = {No\u00e9mi Gask\u00f3 and M. Suciu and R. Lung and Tam\u00e1s K\u00e9pes},\n booktitle = {Logic Journal of the IGPL},\n title = {A Pseudo-Deterministic Noisy Extremal Optimization algorithm for the pairwise connectivity Critical Node Detection Problem},\n year = {2024}\n}<\/pre>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>The critical node detection problem is a central task in computational graph theory due to its large applicability, consisting in deleting $k$ nodes to minimize a certain graph measure. In this article, we propose a new Extremal Optimization-based approach, the Pseudo-Deterministic Noisy Extremal Optimization (PDNEO) algorithm, to solve the Critical Node Detection variant in which the pairwise connectivity is minimized. PDNEO uses an adaptive pseudo-deterministic parameter to switch between random nodes and articulation points during the search, as well as other features, such as noise induction to preserve diversity, greedy search to better exploit the search space and a greater search space exploration mechanism. Numerical experiments on synthetic and real-world networks show the effectiveness of the proposed algorithm compared with existing methods.<\/p>\n","protected":false},"author":6,"featured_media":0,"comment_status":"closed","ping_status":"","sticky":false,"template":"","format":"standard","meta":[],"categories":[4],"tags":[8,18,20,83],"_links":{"self":[{"href":"https:\/\/www.cs.ubbcluj.ro\/~meco\/wp-json\/wp\/v2\/posts\/1237"}],"collection":[{"href":"https:\/\/www.cs.ubbcluj.ro\/~meco\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.cs.ubbcluj.ro\/~meco\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.cs.ubbcluj.ro\/~meco\/wp-json\/wp\/v2\/users\/6"}],"replies":[{"embeddable":true,"href":"https:\/\/www.cs.ubbcluj.ro\/~meco\/wp-json\/wp\/v2\/comments?post=1237"}],"version-history":[{"count":1,"href":"https:\/\/www.cs.ubbcluj.ro\/~meco\/wp-json\/wp\/v2\/posts\/1237\/revisions"}],"predecessor-version":[{"id":1443,"href":"https:\/\/www.cs.ubbcluj.ro\/~meco\/wp-json\/wp\/v2\/posts\/1237\/revisions\/1443"}],"wp:attachment":[{"href":"https:\/\/www.cs.ubbcluj.ro\/~meco\/wp-json\/wp\/v2\/media?parent=1237"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.cs.ubbcluj.ro\/~meco\/wp-json\/wp\/v2\/categories?post=1237"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.cs.ubbcluj.ro\/~meco\/wp-json\/wp\/v2\/tags?post=1237"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}