algorithms  
Selected Algorithmic Papers from the International Workshop on Combinatorial Algorithms 2024  
[PERSON]  
Department of Computer Science, University of Salemo, 84084 Fisciano, Italy; [EMAIL_ADDRESS]  
This Special Issue is dedicated to a selection of papers from the 35 th International Workshop on Combinatorial Algorithms (IWOCA 2024), held in July 2024, in Ischia, Italy, with [PERSON] and [PERSON] as Program Co-chairs. IWOCA is devoted to the broad area of combinatorial algorithms. The topics include algorithms and data structures, algorithms on strings and graphs, algorithms for big data and network analytics, algorithmic game theory, approximation algorithms, combinatorial generation, enumeration and counting, combinatorial optimization, complexity theory, combinatorics of words, computational algebra and geometry, computational biology, cryptography and information security, distributed and parallel algorithms, foundations of cloud computing, graph algorithms for social network analysis, graph drawing and labeling, graph theory and combinatorics, mobile agent, new paradigms of computation, online algorithms, parameterized and exact algorithms, probabilistic and randomized algorithms, and scheduling. A selected group of authors were invited to submit an extended version of the conference publication to this Special Issue. However, the Special Issue was also open to papers that were not presented at the conference if they fell within the scope of the Issue. After a rigorous peer review process in accordance with the high standards of the journal, the following five papers were selected for publication in this Special Issue. The paper \"Enumerating Minimal Vertex Covers and Dominating Sets with Capacity and/or Connectivity Constraints\", by [PERSON], [PERSON], [PERSON], [PERSON], and [PERSON], considers the minimal vertex cover and minimal dominating sets with capacity and/or connectivity constraint enumeration problems. The authors develop polynomial delay enumeration algorithms for these problems on bounded degree graphs. For the case of minimal connected vertex covers, their algorithms run in polynomial delay, even in the class of \(d\)-claw-free graphs. This result is extended for bounded degree graphs and outputs in quasi-polynomial time on general graphs. To complement these algorithmic results, they show that the minimal connected vertex cover, minimal connected dominating set, and minimal capacitated vertex cover enumeration problems in 2-degenerated bipartite graphs are at least as hard as enumerating minimal transversals in hypergraphs. The paper \"Broadcasting in Stars of Cliques and Path-Connected Cliques\", by [PERSON] and [PERSON], examined the broadcasting problem in network topologies represented by specialized clique-based structures. The primary objective was to propose an efficient algorithm for determining the broadcast time of any node in an arbitrary star of cliques and to rigorously prove its optimality. Additionally, the authors considered the broadcasting problem in path-connected cliques. For this structure, they developed a computationally efficient algorithm that leverages clique sizes and adjacency to optimize broadcast strategies, with broader implications for understanding communication in block graphs. The paper \"Perfect Roman Domination: Aspects of Enumeration and Parameterization\", by [PERSON] and [PERSON], presents two ways to translate perfect code into the framework of Roman Dominating Functions. It discusses Perfect Roman Dominating Functions and Unique Response Roman Dominating Functions. The authors considered the complexity of the underlying decision problems on special graph classes. They proved that for split graphs, Unique Response Roman Dominating is polynomial time-solvable, while Perfect Roman Dominating is NP-complete. Beyond this, the authors give polynomial time algorithms for Perfect Roman Domination on interval graphs and for both decision problems on co-bipartite graphs. However, both problems are NP-complete on chordal bipartite graphs.