Journal of Graph Algorithms and Applications
https://www.jgaa.info/index.php/jgaa
<p>The <span class="emph">Journal of Graph Algorithms and Applications</span> (<span class="emph">JGAA</span>) is a peer-reviewed scientific journal devoted to the publication of high-quality research papers on the analysis, design, implementation, and applications of graph algorithms. <span class="emph">JGAA</span> is supported by distinguished advisory and editorial boards, has high scientific standards and is distributed in electronic form. <span style="font-size: 0.875rem;"> </span><span class="emph">JGAA</span> is a diamond open access journal that charges no author fees. Also, <span style="font-size: 0.875rem;">JGAA is </span><a style="background-color: #ffffff; font-size: 0.875rem;" href="https://dblp.org/db/journals/jgaa/index.html" data-auth="NotApplicable" data-linkindex="5">indexed by DBLP</a><span style="font-size: 0.875rem;">.</span></p>en-USfabrizio.montecchiani@unipg.it (Publishing Editor) ( )Tue, 10 Sep 2024 16:00:07 +0000OJS 3.3.0.18http://blogs.law.harvard.edu/tech/rss60Special Issue on WALCOM 2023: Guest Editors' Foreword
https://www.jgaa.info/index.php/jgaa/article/view/2965
<p>Special Issue on WALCOM 2023: Guest Editors' Foreword</p>Chun-Cheng Lin, Bertrand M.-T. Lin, Giuseppe Liotta
Copyright (c) 2024 Chun-Cheng Lin, Bertrand M.-T. Lin, Giuseppe Liotta
https://creativecommons.org/licenses/by/4.0
https://www.jgaa.info/index.php/jgaa/article/view/2965Tue, 10 Sep 2024 00:00:00 +0000Piercing Diametral Disks Induced by Edges of Maximum Spanning Trees
https://www.jgaa.info/index.php/jgaa/article/view/2968
<p>Let $P$ be a set of points in the plane and let $T$ be a maximum-weight spanning tree of $P$.<br />For an edge $(p,q)$, let $D_{pq}$ be the diametral disk induced by $(p,q)$, i.e., the disk having the segment $\overline{pq}$ as its diameter. Let $\cal{D}_T$ be the set of the diametral disks induced by the edges of $T$. <br />In this paper, we show that one point is sufficient to pierce all the disks in $\cal{D}_T$. <br />Actually, we show that the center of the smallest enclosing circle of $P$ is contained in all the disks of $\cal{D}_T$, and thus the piercing point can be computed in linear time.</p>A. Karim Abu-Affash, Paz Carmi, Meytal Maman
Copyright (c) 2024 A. Karim Abu-Affash, Paz Carmi, Meytal Maman
https://creativecommons.org/licenses/by/4.0
https://www.jgaa.info/index.php/jgaa/article/view/2968Tue, 10 Sep 2024 00:00:00 +0000Graph Burning in Community-based Networks
https://www.jgaa.info/index.php/jgaa/article/view/2969
<p>Graph burning is a deterministic, discrete-time process that can be used to model how influence or contagion spreads in a graph. In the graph burning process, each node starts as dormant, and becomes informed/burned over time; when a node is burned, it remains burned until the end of the process. In each round, one can burn a new node (source of fire) in the network. Once a node is burned in round $t$, in round $t+1$, each of its dormant neighbors becomes burned. The process ends when all nodes are burned; the goal is to minimize the number of rounds.<br>We study a variation of graph burning in order to model spreading processes in community-based networks. With respect to a specific piece of information, a community is {\em satisfied} when this information reaches at least a prescribed number of its members. Specifically, we consider the problem of identifying a minimum length sequence of nodes that, according to a graph burning process, allows to satisfy all the communities of the network. <br>We investigate this NP-hard problem from an approximation point of view, showing both a lower bound and a matching upper bound. We also investigate the case when the number of communities is constant and show how to solve the problem with a constant approximation factor.<br>Moreover, we consider the problem of maximizing the number of satisfied groups, given a budget $k$ on the number of rounds.</p>Gennaro Cordasco, Luisa Gargano, Adele A. Rescigno
Copyright (c) 2024 Gennaro Cordasco, Luisa Gargano, Adele A. Rescigno
https://creativecommons.org/licenses/by/4.0
https://www.jgaa.info/index.php/jgaa/article/view/2969Tue, 10 Sep 2024 00:00:00 +0000Splitting Plane Graphs to Outerplanarity
https://www.jgaa.info/index.php/jgaa/article/view/2970
<p>Vertex splitting replaces a vertex by two copies and partitions its incident edges amongst the copies. This problem has been studied as a graph editing operation to achieve desired properties with as few splits as possible, most often planarity, for which the problem is NP-hard.<br />Here we study how to minimize the number of splits to turn a plane graph into an outerplane one. We tackle this problem by establishing a direct connection between splitting a plane graph to outerplanarity, finding a connected face cover, and finding a feedback vertex set in its dual. We prove NP-completeness for plane biconnected graphs, while we show that a polynomial-time algorithm exists for maximal planar graphs. Additionally, we show upper and lower bounds for certain families of maximal planar graphs. Finally, we provide a SAT formulation for the problem, and evaluate it on a small benchmark.</p>Martin Gronemann, Martin Nöllenburg, Anaïs Villedieu
Copyright (c) 2024 Martin Gronemann, Martin Nöllenburg, Anaïs Villedieu
https://creativecommons.org/licenses/by/4.0
https://www.jgaa.info/index.php/jgaa/article/view/2970Tue, 10 Sep 2024 00:00:00 +0000Certifying Induced Subgraphs in Large Graphs
https://www.jgaa.info/index.php/jgaa/article/view/2971
<p>We introduce I/O-efficient certifying algorithms for the recognition of bipartite, split, threshold, bipartite chain, and trivially perfect graphs. <br>When the input graph is a member of the respective class, the certifying algorithm returns a certificate that characterizes this class.<br>Otherwise, it returns a forbidden induced subgraph as a certificate for non-membership.<br>On a graph with $n$ vertices and $m$ edges, our algorithms take $\mathcal O(\text{sort}(n + m))$ I/Os in the worst case for split, threshold and trivially perfect graphs.<br>In the same complexity bipartite and bipartite chain graphs can be certified with high probability.<br>We provide implementations and an experimental evaluation for split and threshold graphs.</p>Ulrich Meyer, Hung Tran, Konstantinos Tsakalidis
Copyright (c) 2024 Ulrich Meyer, Hung Tran, Konstantinos Tsakalidis
https://creativecommons.org/licenses/by/4.0
https://www.jgaa.info/index.php/jgaa/article/view/2971Tue, 10 Sep 2024 00:00:00 +0000Some Algorithmic Results for Eternal Vertex Cover Problem in Graphs
https://www.jgaa.info/index.php/jgaa/article/view/2972
<p>The eternal vertex cover problem is a variant of the vertex cover problem. It is a two-player (attacker and defender) game in which, given a graph $G=(V,E)$, the defender needs to allocate guards at some vertices so that the allocated vertices form a vertex cover. The attacker can attack one edge at a time, and the defender needs to move the guards along the edges such that at least one guard moves through the attacked edge and the new configuration still remains a vertex cover. The attacker wins if no such move exists for the defender. The defender wins if there exists a strategy to defend the graph against infinite sequence of attacks. The minimum number of guards with which the defender can form a winning strategy is called the <em>eternal vertex cover number</em> of $G$, and is denoted by $evc(G)$. Given a graph $G$, the problem of finding the eternal vertex cover number is NP-hard for general graphs and remains NP-hard even for bipartite graphs. We have given a polynomial time algorithm to find the Eternal vertex cover number in chain graphs and $P_4$-sparse graphs. We have also given a linear-time algorithm to find the eternal vertex cover number for split graphs, an important subclass of chordal graphs.</p>Kaustav Paul, Arti Pandey
Copyright (c) 2024 Kaustav Paul, Arti Pandey
https://creativecommons.org/licenses/by/4.0
https://www.jgaa.info/index.php/jgaa/article/view/2972Tue, 10 Sep 2024 00:00:00 +0000Reconfiguration of vertex-disjoint shortest paths on graphs
https://www.jgaa.info/index.php/jgaa/article/view/2973
<p>We introduce and study reconfiguration problems for (internally) vertex-disjoint shortest paths:<br>Given two tuples of internally vertex-disjoint shortest paths for fixed terminal pairs in an unweighted graph, we are asked to determine whether one tuple can be transformed into the other by exchanging a single vertex of one shortest path in the tuple at a time, so that all intermediate results remain tuples of internally vertex-disjoint shortest paths.<br>We also study the shortest variant of the problem, that is, we wish to minimize the number of vertex-exchange steps required for such a transformation, if exists. <br>These problems generalize the well-studied Shortest Path Reconfiguration problem. <br>In this paper, we analyze the complexity of these problems from the viewpoint of graph classes, and give some interesting contrast.</p>Rin Saito, Hiroshi Eto, Takehiro Ito, Ryuhei Uehara
Copyright (c) 2024 Rin Saito, Hiroshi Eto, Takehiro Ito, Ryuhei Uehara
https://creativecommons.org/licenses/by/4.0
https://www.jgaa.info/index.php/jgaa/article/view/2973Tue, 10 Sep 2024 00:00:00 +0000