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

Format:

Book

Author/Creator:

Rescigno, Adele Anna.

Contributor:

Vaccaro, Ugo.

Series:

Lecture Notes in Computer Science, 1611-3349 ; 14764

Language:

English

Subjects (All):

Computer science--Mathematics.

Computer science.

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.

Local Subjects:

Discrete Mathematics in Computer Science.

Computer Engineering and Networks.

Design and Analysis of Algorithms.

Data Structures and Information Theory.

Computer Graphics.

Numerical Analysis.

Physical Description:

1 online resource (557 pages)

Edition:

1st ed. 2024.

Place of Publication:

Cham : Springer Nature Switzerland : Imprint: Springer, 2024.

Summary:

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.

Contents:

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.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&gt

=6)

5 Open Questions

Weighted Group Search on the Disk and Improved LP-Based Lower Bounds for Priority Evacuation

1.1 Related Work

1.2 Discussion on New Results

1.3 Key Technical and Conceptual Ideas

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

Simple Random Sampling of Binary Forests with Fixed Number of Nodes and Trees

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

Maximizing Minimum Cycle Bases Intersection

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

Improving Online Bin Covering with Little Advice

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

An Improved Bound for Equitable Proper Labellings

2 Proof of Theorem 1

3 Conclusion

Approximate Realizations for Outerplanaric Degree Sequences

3 Necessary and Sufficient Conditions for Outerplanarity

4 Approximate Realizations by Book Embeddings

Hypergraph Dualization with FPT-delay Parameterized by the Degeneracy and Dimension

3 Ordered Generation

4 Parameterized Children Generation

5 Consequences for Minimal Domination

6 Discussion and Limitations

Star-Forest Decompositions of Complete Graphs

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

Convex-Geometric k-Planar Graphs Are Convex-Geometric (k+1)-Quasiplanar

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

Detecting K2,3 as an Induced Minor

3 Reducing to Truemper Configurations

4 Detecting 3-Path-Configurations

5 Detecting a Broken Wheel

6 Conclusion

Computing Maximal Palindromes in Non-standard Matching Models

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

On the Structure of Hamiltonian Graphs with Small Independence Number

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

Resolving Unresolved Resolved and Unresolved Triplets Consistency Problems

3 The F+ Consistency Problem for a Ternary Tree

4 The Remaining Ternary Consistency Problems

5 Conclusion

Complexity Framework for Forbidden Subgraphs IV: The Steiner Forest Problem

2 NP-Completeness Results

3 Polynomial Subroutines

4 Polynomial Cases

Minimizing Distances Between Vertices and Edges Through Tree t-Spanners

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

Enumerating Minimal Vertex Covers and Dominating Sets with Capacity and/or Connectivity Constraints

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

Making the Interval Membership Width of Temporal Graphs Connected and Bidirectional

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

Efficient Algorithms for Decomposing Integers as Sums of Few Tetrahedral Numbers

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

Approximation Algorithms for Node-Weighted Directed Steiner Problems

2 Notation and Problem Statement

3 Directed Rooted Tree Problems

4 Discussion and Future Work

Resolving Sets in Temporal Graphs

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

On the Finiteness of k-Vertex-Critical 2P2-Free Graphs with Forbidden Induced Squids or Bulls

1.1 Outline

1.2 Notation

3 (2P2, bull)-Free

4 (2P2, (4,)-squid)-Free

5 (2P2, (3,)-squid)-Free

6 Exhaustive Generation for Small k

Directed Path Partition Problem on Directed Acyclic Graphs

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

Computing Minimal Absent Words and Extended Bispecial Factors with CDAWG Space

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

Lower Bounds for Leaf Rank of Leaf Powers

2 Basic Notions

3 Construction of Rn

4 The Graph Class {Rn n3} has Exponential Leaf Rank

Perfect Roman Domination: Aspects of Enumeration and Parameterization

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

Computing Longest Common Subsequence Under Cartesian-Tree Matching Model.

1 Introduction.

Other Format:

Print version: Rescigno, Adele Anna Combinatorial Algorithms

ISBN:

9783031630217

OCLC:

1442495806