Combinatorial Algorithms : 35th International Workshop, IWOCA 2024, Ischia, Italy, July 1–3, 2024, Proceedings / / edited by Adele Anna Rescigno, Ugo Vaccaro

• Autore: Rescigno Adele Anna
• Pubblicazione: Cham : , : Springer Nature Switzerland : , : Imprint : Springer, , 2024
• Edizione: 1st ed. 2024.
• Descrizione fisica: 1 online resource (557 pages)
• Disciplina: 004.0151
• Soggetto topico: Computer science - Mathematics; Discrete mathematics; Computer engineering; Computer networks; Algorithms; Data structures (Computer science); Information theory; Computer graphics; Numerical analysis; Discrete Mathematics in Computer Science; Computer Engineering and Networks; Design and Analysis of Algorithms; Data Structures and Information Theory; Computer Graphics; Numerical Analysis
• Altri autori: VaccaroUgo
• Nota di contenuto: Intro -- Preface -- Organization -- Abstracts of Invited Talks -- Bamboo Garden Trimming Problem -- Cover-Free Families and Generalizations Based on Hypergraphs -- ED-Strings Similarities for PanGenomes Comparison -- Contents -- On Computing Sets of Integers with Maximum Number of Pairs Summing to Powers of 2 -- 1 Introduction -- 2 Algorithm for Testing Graph Admissibility -- 3 Solving a System of (in)equations in Powers of 2 -- 4 Minimal Forbidden Subgraphs -- 5 Computing Values of g(n) -- 6 Maximum Admissible Graphs -- 7 Discussion -- References -- Matchings in Hypercubes Extend to Long Cycles -- 1 Introduction -- 1.1 Our Results -- 1.2 Applications to Hamilton-Laceability -- 1.3 Avoiding and Including Other Structures -- 1.4 Outline of This Paper -- 2 Preliminaries -- 2.1 Notation and Definitions -- 2.2 Auxiliary Lemmas -- 3 Proof of Theorem 5 -- 4 Proof of Theorem 8 -- 4.1 Forward Implication -- 4.2 Reverse Implication (Induction Step d-1 to d for d> -- =6) -- 5 Open Questions -- References -- Weighted Group Search on the Disk and Improved LP-Based Lower Bounds for Priority Evacuation -- 1 Introduction -- 1.1 Related Work -- 1.2 Discussion on New Results -- 1.3 Key Technical and Conceptual Ideas -- 2 Preliminaries -- 2.1 Problem Definition, Notation and Some Observations -- 2.2 Past Results, Search Domains and Cost Functions -- 3 Improved Framework for Proving Lower Bounds -- 4 Implied (and Improved) Lower Bounds for Priority Evacuation -- 5 Weighted Group Search on the Disk -- 5.1 Upper Bounds to Weighted Group Search on the Disk -- 5.2 Lower Bounds to Weighted Group Search on the Disk -- References -- Simple Random Sampling of Binary Forests with Fixed Number of Nodes and Trees -- 1 Introduction -- 1.1 Problem, Notation and Motivation -- 1.2 Previous Work on Generation of Random Trees and Forests -- 2 Bijection for Binary Forests. ; 3 Linear Time Algorithm for Random Sampling of Forests -- References -- Maximizing Minimum Cycle Bases Intersection -- 1 Introduction -- 2 Formal Definitions -- 3 Case with k = 2, Approximability and Parameterized Complexity -- 4 Hardness of MCBI -- 5 Cases = 3, and = 4, = 3 -- 6 Concluding Remarks -- References -- Improving Online Bin Covering with Little Advice -- 1 Introduction -- 2 Preliminaries -- 3 Description of the Previous Strategies with Improvements -- 4 Modification and Analysis of the Boyar et al. Strategy -- 4.1 Placing the 2-Items -- 4.2 Placing the Small Items -- 5 Conclusions -- References -- An Improved Bound for Equitable Proper Labellings -- 1 Introduction -- 2 Proof of Theorem 1 -- 3 Conclusion -- References -- Approximate Realizations for Outerplanaric Degree Sequences -- 1 Introduction -- 2 Preliminaries -- 3 Necessary and Sufficient Conditions for Outerplanarity -- 4 Approximate Realizations by Book Embeddings -- References -- Hypergraph Dualization with FPT-delay Parameterized by the Degeneracy and Dimension -- 1 Introduction -- 2 Preliminaries -- 3 Ordered Generation -- 4 Parameterized Children Generation -- 5 Consequences for Minimal Domination -- 6 Discussion and Limitations -- References -- Star-Forest Decompositions of Complete Graphs -- 1 Introduction -- 2 Decompositions of Complete Graphs into Star-Forests -- 3 Decomposing Complete Geometric Graphs into Plane Star-Forests -- 4 Computing Plane Star-Forest Decompositions on Small Point Sets -- 5 Further Research and Open Questions -- References -- Convex-Geometric k-Planar Graphs Are Convex-Geometric (k+1)-Quasiplanar -- 1 Introduction -- 1.1 Contribution -- 1.2 Organization of the Paper -- 2 Notation -- 3 (k+1)-Crossings in Convex-Geometric K-Planar Graphs -- 4 The Flipping Operation -- 5 Linear Order on the (k+1)-Crossings -- 6 The Global Flip. ; 7 Convex-Geometric K-Quasiplanarity -- 8 Open Questions -- References -- Detecting K2,3 as an Induced Minor -- 1 Introduction -- 2 Preliminaries -- 3 Reducing to Truemper Configurations -- 4 Detecting 3-Path-Configurations -- 5 Detecting a Broken Wheel -- 6 Conclusion -- References -- Computing Maximal Palindromes in Non-standard Matching Models -- 1 Introduction -- 2 Preliminaries -- 2.1 Notations -- 2.2 Substring Consistent Symmetric and Two-Transitive Relation -- 2.3 Our Problems -- 3 Algorithms for Computing Maximal SCSTTR Symmetry-Based Palindromes -- 4 Algorithms for Computing Maximal SCSTTR Reversal-Based Palindromes -- 4.1 Outline of Computing SCSTTR Reversal-Based Palindromes -- 4.2 Maximal Theta Reversal-Based Palindromes -- 4.3 Maximal Cartesian-Tree Reversal-Based Palindromes -- References -- On the Structure of Hamiltonian Graphs with Small Independence Number -- 1 Introduction -- 2 Preliminaries -- 3 Hamiltonian Paths in Graphs with Small Independence Number -- 3.1 3K1-Free Graphs -- 3.2 4K1-Free Graphs -- 3.3 5K1-Free Graphs -- 4 Conclusion -- References -- Resolving Unresolved Resolved and Unresolved Triplets Consistency Problems -- 1 Introduction -- 2 Preliminaries -- 3 The F+ Consistency Problem for a Ternary Tree -- 4 The Remaining Ternary Consistency Problems -- 5 Conclusion -- References -- Complexity Framework for Forbidden Subgraphs IV: The Steiner Forest Problem -- 1 Introduction -- 2 NP-Completeness Results -- 3 Polynomial Subroutines -- 4 Polynomial Cases -- 5 Conclusions -- References -- Minimizing Distances Between Vertices and Edges Through Tree t-Spanners -- 1 Introduction -- 2 Bounds on Edge and Total Admissibility -- 3 Total Admissibility -- 3.1 Total k-Admissibility is NP-Complete -- 3.2 Total 4-Admissible Graphs -- 4 Clique-Augmenting Graphs -- 4.1 Clique-Augmenting Graphs on Cliques of Size 2. ; 4.2 Clique-Augmenting Planar Graphs on Cliques of Size 3 -- 4.3 Clique-Augmenting Line Graphs on Cliques of Arbitrary Sizes -- 5 Further Work -- References -- Enumerating Minimal Vertex Covers and Dominating Sets with Capacity and/or Connectivity Constraints -- 1 Introduction -- 2 Preliminaries -- 3 A Quick Tour of the Supergraph Technique -- 4 Minimal Connected Vertex Cover Enumeration -- 5 Minimal Connected Dominating Set Enumeration -- 6 Capacitated Vertex Cover and Dominating Set -- 7 Concluding Remarks -- References -- Making the Interval Membership Width of Temporal Graphs Connected and Bidirectional -- 1 Introduction -- 2 Connected (Vertex) Interval Membership Width -- 3 Eulerian Trails Parameterized by imw and by imw -- 4 Vertex Coloring Parameterized by imw and by imw -- 5 Firefighter Parameterized by vimw -- 6 Bidirectional Connected Interval Membership Width -- 7 Conclusion -- References -- Efficient Algorithms for Decomposing Integers as Sums of Few Tetrahedral Numbers -- 1 Introduction -- 2 Expressing Integers as Sums of at Most Eight Tetrahedral Numbers -- 2.1 Computing a Proper m -- 2.2 Computing x and y -- 2.3 Representing 8k+3 as a Sum of Three Squares -- 3 Expressing Each Integer as a Sum of the Fewest Possible Tetrahedral Numbers -- 3.1 A Simple Algorithm Based on Conjecture 1 and the Pollock's Conjecture -- 3.2 Reducing the Space from O() to O(2/3) -- 3.3 Empirical Verification of Conjecture 1 -- 3.4 Verification of the Pollock's Conjecture up to 1020 -- 4 Conclusion -- References -- Approximation Algorithms for Node-Weighted Directed Steiner Problems -- 1 Introduction -- 2 Notation and Problem Statement -- 3 Directed Rooted Tree Problems -- 4 Discussion and Future Work -- References -- Resolving Sets in Temporal Graphs -- 1 Introduction -- 2 NP-Hardness of Temporal Resolving Set. ; 3 Polynomial-Time Algorithms for Subclasses of Trees -- 3.1 Temporal Paths -- 3.2 Temporal Stars -- 4 Combinatorial Results for p-Periodic 1-Labelings -- 5 Conclusion -- References -- On the Finiteness of k-Vertex-Critical 2P2-Free Graphs with Forbidden Induced Squids or Bulls -- 1 Introduction -- 1.1 Outline -- 1.2 Notation -- 2 Preliminaries -- 3 (2P2, bull)-Free -- 4 (2P2, (4,)-squid)-Free -- 5 (2P2, (3,)-squid)-Free -- 6 Exhaustive Generation for Small k -- 7 Conclusion -- References -- Directed Path Partition Problem on Directed Acyclic Graphs -- 1 Introduction -- 2 Preliminaries -- 3 Degree 3 and Height k+1 -- 4 Tractable Cases for k-PP -- 4.1 DAGs of Height at Most k -- 4.2 Directed Graphs of Degree at Most Two -- References -- Computing Minimal Absent Words and Extended Bispecial Factors with CDAWG Space -- 1 Introduction -- 2 Preliminaries -- 2.1 Basic Notations -- 2.2 MAW, MUS, MRW, and EBF -- 2.3 Maximal Substrings and Maximal Repeats -- 2.4 CDAWG -- 3 CDAWG Grammars -- 4 Computing MAWs and EBFs with CDAWG -- 4.1 Computing MAWs -- 4.2 Computing EBFs -- 4.3 Computing Length-Bounded MAWs and EBFs -- 5 Computing MRWs -- 6 Conclusions and Future Work -- References -- Lower Bounds for Leaf Rank of Leaf Powers -- 1 Introduction -- 2 Basic Notions -- 3 Construction of Rn -- 4 The Graph Class {Rn n3} has Exponential Leaf Rank -- 5 Conclusion -- References -- Perfect Roman Domination: Aspects of Enumeration and Parameterization -- 1 Introduction -- 2 Enumerating Minimal Perfect Roman Domination -- 3 Complexity and Enumeration in Special Graph Classes -- 3.1 Interval Graphs -- 3.2 Split Graphs -- 3.3 Cobipartite Graphs -- 3.4 Remarks on Enumeration of urRdfs in Split Graphs -- 3.5 Chordal Bipartite Graphs -- 4 Parameterized Complexity -- 5 Final Remarks -- References -- Computing Longest Common Subsequence Under Cartesian-Tree Matching Model. ; 1 Introduction.
• Sommario/riassunto: This book constitutes the refereed proceedings of the 35th International Workshop on Combinatorial Algorithms, IWOCA 2024, held in Ischia, Italy, during July 1–3, 2024. The 40 full papers included in this book were carefully reviewed and selected from 110 submissions. The IWOCA conference series has provided an annual forum for researchers who design algorithms to address the myriad combinatorial problems underlying computer applications in science, engineering, and business.
• Titolo autorizzato: Combinatorial Algorithms
• ISBN: 9783031630217; 9783031630200
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 9910866566803321
• Lo trovi qui: Univ. Federico II
• Serie: Lecture Notes in Computer Science, . 1611-3349 ; ; 14764