Info
Combinatorial Algorithms : 35th International Workshop, IWOCA 2024, Ischia, Italy, July 1–3, 2024, Proceedings / / edited by Adele Anna Rescigno, Ugo Vaccaro
| 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 |
| Edizione | [1st ed. 2024.] |
| Pubbl/distr/stampa | Cham : , : Springer Nature Switzerland : , : Imprint : Springer, , 2024 |
| Descrizione fisica | 1 online resource (557 pages) |
| Disciplina | 004.0151 |
| Altri autori (Persone) | VaccaroUgo |
| Collana | Lecture Notes in Computer Science |
| 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 |
| ISBN |
9783031630217
9783031630200 |
| Formato | Materiale a stampa  |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| 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. |
| Record Nr. | UNINA-9910866566803321 |
Rescigno Adele Anna
|
||
| Cham : , : Springer Nature Switzerland : , : Imprint : Springer, , 2024 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Combinatorial Pattern Matching [[electronic resource] ] : 26th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29 -- July 1, 2015, Proceedings / / edited by Ferdinando Cicalese, Ely Porat, Ugo Vaccaro
| Combinatorial Pattern Matching [[electronic resource] ] : 26th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29 -- July 1, 2015, Proceedings / / edited by Ferdinando Cicalese, Ely Porat, Ugo Vaccaro |
| Edizione | [1st ed. 2015.] |
| Pubbl/distr/stampa | Cham : , : Springer International Publishing : , : Imprint : Springer, , 2015 |
| Descrizione fisica | 1 online resource (XIX, 412 p. 69 illus.) |
| Disciplina | 005.1 |
| Collana | Theoretical Computer Science and General Issues |
| Soggetto topico |
Pattern recognition systems
Algorithms Numerical analysis Computer science—Mathematics Discrete mathematics Artificial intelligence—Data processing Bioinformatics Automated Pattern Recognition Numerical Analysis Discrete Mathematics in Computer Science Data Science Computational and Systems Biology |
| ISBN | 3-319-19929-3 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | On the Hardness of Optimal Vertex Relabeling and Restricted Vertex Relabeling -- A Framework for Space-Efficient String Kernels -- Composite Repetition-Aware Data Structures -- Efficient Construction of a Compressed de Bruijn Graph for Pan-Genome Analysis -- Longest Common Extensions in Trees -- Longest Common Extensions in Sublinear Space -- Ranked Document Retrieval with Forbidden Pattern -- Parameterized Complexity of Superstring Problems -- On the Fixed Parameter Tractability and Approximability of the Minimum Error Correction Problem -- Fast String Dictionary Lookup with One Error -- On the Readability of Overlap Digraphs -- Improved Algorithms for the Boxed-Mesh Permutation Pattern Matching Problem -- Range Minimum Query Indexes in Higher Dimensions -- Alphabet-Dependent String Searching with Wexponential Search Trees -- Lempel Ziv Computation in Small Space (LZ-CISS) -- Succinct Non-overlapping Indexing -- Encodings of Range Maximum-Sum Segment Queries and Applications -- Compact Indexes for Flexible Top-k Retrieval -- LZD Factorization: Simple and Practical Online Grammar Compression with Variable-to-Fixed Encoding -- Combinatorial RNA Design: Designability and Structure-Approximating Algorithm -- Dictionary Matching with Uneven Gaps -- Partition into Heapable Sequences, Heap Tableaux and a Multiset Extension of Hammersley’s Process -- The Approximability of Maximum Rooted Triplets Consistency with Fan Triplets and Forbidden Triplets -- String Powers in Trees -- Online Detection of Repetitions with Backtracking -- Greedy Conjecture for Strings of Length 4 -- Tighter Bounds for the Sum of Irreducible LCP Values -- Parallel External Memory Suffix Sorting -- On Maximal Unbordered Factors -- Semi-dynamic Compact Index for Short Patterns and Succinct van Emde Boas Tree -- Reporting Consecutive Substring Occurrences Under Bounded Gap Constraints -- A Probabilistic Analysis of the Reduction Ratio in the Suffix-Array IS Algorithm -- Encoding Nearest Larger Values -- Sorting by Cuts, Joins and Whole Chromosome Duplications. |
| Record Nr. | UNISA-996198521103316 |
| Cham : , : Springer International Publishing : , : Imprint : Springer, , 2015 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Combinatorial Pattern Matching : 26th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29 -- July 1, 2015, Proceedings / / edited by Ferdinando Cicalese, Ely Porat, Ugo Vaccaro
| Combinatorial Pattern Matching : 26th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29 -- July 1, 2015, Proceedings / / edited by Ferdinando Cicalese, Ely Porat, Ugo Vaccaro |
| Edizione | [1st ed. 2015.] |
| Pubbl/distr/stampa | Cham : , : Springer International Publishing : , : Imprint : Springer, , 2015 |
| Descrizione fisica | 1 online resource (XIX, 412 p. 69 illus.) |
| Disciplina | 005.1 |
| Collana | Theoretical Computer Science and General Issues |
| Soggetto topico |
Pattern recognition systems
Algorithms Numerical analysis Computer science—Mathematics Discrete mathematics Artificial intelligence—Data processing Bioinformatics Automated Pattern Recognition Numerical Analysis Discrete Mathematics in Computer Science Data Science Computational and Systems Biology |
| ISBN | 3-319-19929-3 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | On the Hardness of Optimal Vertex Relabeling and Restricted Vertex Relabeling -- A Framework for Space-Efficient String Kernels -- Composite Repetition-Aware Data Structures -- Efficient Construction of a Compressed de Bruijn Graph for Pan-Genome Analysis -- Longest Common Extensions in Trees -- Longest Common Extensions in Sublinear Space -- Ranked Document Retrieval with Forbidden Pattern -- Parameterized Complexity of Superstring Problems -- On the Fixed Parameter Tractability and Approximability of the Minimum Error Correction Problem -- Fast String Dictionary Lookup with One Error -- On the Readability of Overlap Digraphs -- Improved Algorithms for the Boxed-Mesh Permutation Pattern Matching Problem -- Range Minimum Query Indexes in Higher Dimensions -- Alphabet-Dependent String Searching with Wexponential Search Trees -- Lempel Ziv Computation in Small Space (LZ-CISS) -- Succinct Non-overlapping Indexing -- Encodings of Range Maximum-Sum Segment Queries and Applications -- Compact Indexes for Flexible Top-k Retrieval -- LZD Factorization: Simple and Practical Online Grammar Compression with Variable-to-Fixed Encoding -- Combinatorial RNA Design: Designability and Structure-Approximating Algorithm -- Dictionary Matching with Uneven Gaps -- Partition into Heapable Sequences, Heap Tableaux and a Multiset Extension of Hammersley’s Process -- The Approximability of Maximum Rooted Triplets Consistency with Fan Triplets and Forbidden Triplets -- String Powers in Trees -- Online Detection of Repetitions with Backtracking -- Greedy Conjecture for Strings of Length 4 -- Tighter Bounds for the Sum of Irreducible LCP Values -- Parallel External Memory Suffix Sorting -- On Maximal Unbordered Factors -- Semi-dynamic Compact Index for Short Patterns and Succinct van Emde Boas Tree -- Reporting Consecutive Substring Occurrences Under Bounded Gap Constraints -- A Probabilistic Analysis of the Reduction Ratio in the Suffix-Array IS Algorithm -- Encoding Nearest Larger Values -- Sorting by Cuts, Joins and Whole Chromosome Duplications. |
| Record Nr. | UNINA-9910483208003321 |
| Cham : , : Springer International Publishing : , : Imprint : Springer, , 2015 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||