SOFSEM 2023, theory and practice of computer science : 48th international conference on current trends in theory and practice of computer science, SOFSEM 2023, Nový Smokovec, Slovakia, January 15-18, 2023, proceedings / / edited by Leszek Gąsieniec

• Pubblicazione: Cham, Switzerland : , : Springer, , [2023]; ©2023
• Descrizione fisica: 1 online resource (401 pages)
• Disciplina: 004
• Soggetto topico: Computer science
• Persona (resp. second.): GąsieniecLeszek
• Nota di bibliografia: Includes bibliographical references and index.
• Nota di contenuto: Intro -- Preface -- Organization -- Contents -- Graphs Problems and Optimisation -- The Complexity of Finding Tangles -- 1 Introduction -- 2 Exact Algorithms -- 3 Complexity -- 4 Counterexample to Conjecture 1 -- References -- A Spectral Algorithm for Finding Maximum Cliques in Dense Random Intersection Graphs -- 1 Introduction -- 1.1 Previous Work on Maximum Cliques in Random Intersection Graphs -- 2 Our Contribution -- 3 Definitions, Notation and Useful Results -- 3.1 Range of Values for m,n,p -- 4 The Spectral Algorithm -- 4.1 Running Time of Our Algorithm -- 5 Experimental Evaluation -- 6 Conclusions -- 7 Appendix -- 7.1 Greedy-Clique Algorithm -- 7.2 Mono-Clique Algorithm -- 7.3 Maximum-Clique Algorithm -- References -- Solving Cut-Problems in Quadratic Time for Graphs with Bounded Treewidth -- 1 Introduction -- 2 Related Work -- 3 Preliminaries -- 4 Max-Bisection: From O(2t n3) to O(2tn2) -- 5 Our Framework -- 6 Conclusion -- References -- More Effort Towards Multiagent Knapsack -- 1 Introduction -- 2 Hardness of Median-UK -- 3 Algorithms for Special Cases -- 3.1 When = 1: Diverse Knapsack -- 4 Conclusion -- References -- Graph Drawing and Visualization -- Dominance Drawings for DAGs with Bounded Modular Width -- 1 Introduction -- 2 Preliminaries -- 3 The Compaction Lemma -- 4 Minimizing the Number of Fips -- 5 Minimizing the Number of Dimensions -- 6 Concluding Remarks -- References -- Morphing Planar Graph Drawings Through 3D -- 1 Introduction -- 2 An Upper Bound -- 2.1 3D Morph Operations -- 2.2 3D Morphs for Biconnected Planar Graphs -- 2.3 3D Morphs for General Planar Graphs -- 3 Discussion: Lower Bounds -- 4 Open Problems -- References -- Visualizing Multispecies Coalescent Trees: Drawing Gene Trees Inside Species Trees -- 1 Introduction -- 2 Drawing Style -- 3 NP-Hardness -- 4 Planar Instances -- 5 Algorithms -- References. ; Parameterized Approaches to Orthogonal Compaction -- 1 Introduction -- 2 Basic Definitions -- 3 Number of Kitty Corners: An FPT Algorithm -- 4 A Polynomial Kernel for Cycle Graphs -- 5 Maximum Face Degree: Parameterized Hardness -- 6 Height of the Representation: An XP Algorithm -- 7 Open Problems -- References -- NP-Hardness and Fixed Parameter Tractability -- Hardness of Bounding Influence via Graph Modification -- 1 Introduction -- 2 Related Work -- 3 Preliminaries -- 3.1 Graph Theoretic Terminology -- 3.2 Centrality Measures -- 4 Bounding the Influence of Vertex Centrality Scores -- References -- Heuristics for Opinion Diffusion via Local Elections -- 1 Introduction -- 1.1 Our Contributions -- 1.2 Related Work -- 2 Formal Model -- 2.1 Opinion Graphs -- 2.2 Campaigning and Bribery -- 2.3 Diffusion Processes via Local Elections -- 2.4 Election Results via Global Voting Rules -- 2.5 Optimization Goals -- 3 Computing Optimal Bribery Schemes -- 3.1 Heuristic Methods -- 4 Simulations -- 4.1 Experimental Design -- 4.2 Results -- 5 Outlook -- References -- On the Parameterized Complexity of s-club Cluster Deletion Problems -- 1 Introduction -- 2 Preliminaries -- 3 Algorithm for s-Club Cluster Edge Deletion -- 3.1 Definition of the Records -- 3.2 Description of the Algorithm -- 4 Algorithm for s-Club Cluster Vertex Deletion -- 5 Discussion and Open Problems -- References -- SOFSEM 2023 Best Papers -- Balanced Substructures in Bicolored Graphs -- 1 Introduction -- 2 NP-hardness Results -- 2.1 Complexity in Split Graphs -- 3 Small Balanced Paths, Trees and Connected Subgraphs -- 4 FPT Algorithms -- 4.1 Randomized Algorithms -- 4.2 Deterministic Algorithms -- 5 Concluding Remarks -- References -- On the Complexity of Scheduling Problems with a Fixed Number of Parallel Identical Machines -- 1 Introduction -- 2 Preliminaries -- 2.1 Subset Sum and Partition. ; 2.2 Scheduling -- 2.3 The Scheduling Lower Bounds by Abboud et al. -- 2.4 Our Results -- 3 Problems with One Machine -- 4 Problems with Multiple Machines -- 5 Conclusion -- References -- SOFSEM 2023 Best Student Papers -- On the 2-Layer Window Width Minimization Problem -- 1 Introduction -- 2 Window Width Minimization with Bottom Layer Fixed -- 3 Window Width Minimization with Top Layer Fixed -- 4 Open Problems -- References -- Sequentially Swapping Tokens: Further on Graph Classes -- 1 Introduction -- 2 Preliminaries -- 3 Polynomial-Time Algorithm for Block-Cactus Graphs -- 3.1 Reduction to a Generalized Problem on Biconnected Components -- 3.2 Sub-STS on cycles -- 3.3 Sub-STS on complete graphs -- 3.4 The Whole Algorithm -- 4 Hardness of the Few-Color and Colorful Cases -- 4.1 General Tools for Showing Hardness -- 4.2 The Few-Color Case on Grid-Like Graphs -- 4.3 The Colorful Case on Grid-Like Graphs -- 5 Concluding Remarks -- References -- Communication and Temporal Graphs -- On the Preservation of Properties When Changing Communication Models -- 1 Introduction -- 2 The FIFO System -- 3 Comparing Channel Layouts -- 4 Property Preservation -- 4.1 Reachability -- 4.2 Deadlock Freedom -- 4.3 Confluence -- 4.4 Summary of Results -- 5 Conclusion -- References -- Introduction to Routing Problems with Mandatory Transitions -- 1 Introduction -- 2 Shortest Path Problems with Mandatory Transitions -- 2.1 Polynomiality of SPMT -- 2.2 Non Approximation of Elementary SPMTand MRMT -- 3 Routing Problems with Mandatory Transitions -- 4 Conclusion -- References -- Payment Scheduling in the Interval Debt Model -- 1 Introduction -- 2 The Interval Debt Model -- 2.1 Formal Setting -- 2.2 Schedules -- 2.3 Problem Definitions -- 3 Our Results -- 3.1 Hardness Results -- 3.2 Polynomial-Time Algorithms -- 4 Conclusion and Open Problems -- References. ; Multi-Parameter Analysis of Finding Minors and Subgraphs in Edge-Periodic Temporal Graphs -- 1 Introduction -- 2 Preliminaries -- 3 Temporal Extension of Graph Problems -- 4 Periodic Character Alignment -- 5 Minors and Subgraphs -- 5.1 Subgraphs -- 5.2 Minors -- 5.3 Further Parameterized Analysis -- 6 Short Traversal -- 7 Conclusion -- References -- Complexity and Learning -- Lower Bounds for Monotone q-Multilinear Boolean Circuits -- 1 Introduction -- 2 Monotone Boolean Circuits and Functions -- 3 Monotone q-multilinear Boolean Circuits -- 3.1 q-multilinearity Versus Bounded Conjunction Depth -- 4 Lower Bounds for q-multilinear Boolean Circuits -- 4.1 Lower Bound Trade-Offs for Semi-disjoint Bilinear Forms -- 4.2 Lower Bounds for Isolk,n -- References -- A Faster Algorithm for Determining the Linear Feasibility of Systems of BTVPI Constraints -- 1 Introduction -- 2 Statement of Problems -- 3 A Rewrite Version of Fourier-Motzkin Elimination -- 4 The BCS Linear Programming Algorithm -- 4.1 Analysis -- 5 Conclusion -- References -- Quantum Complexity for Vector Domination Problem -- 1 Introduction -- 1.1 Prior Work -- 1.2 Our Results -- 2 Preliminaries -- 2.1 Problem Definitions -- 2.2 Quantum Query Model -- 2.3 Techniques -- 3 Vector Domination -- 3.1 Lower Bounds -- 3.2 Upper Bounds -- 4 Minimum Inner Product -- 4.1 Idea -- 4.2 Preprocessing -- 4.3 Reduction -- 5 Open Questions -- References -- Learning Through Imitation by Using Formal Verification -- 1 Introduction -- 2 Related Work -- 3 Method -- 3.1 Q-Learning -- 3.2 Using a Model Checker on the Q-learning Model -- 4 Model Checker as an Expert-Applications -- 4.1 Convergence with Fewer Epochs -- 4.2 Help Convergence by Avoiding Sub-optimal Solutions -- 4.3 Explore Unseen States -- 5 Discussion -- References -- Robots and Strings -- Delivery to Safety with Two Cooperating Robots -- 1 Introduction. ; 1.1 Model, Notation, and Preliminaries -- 1.2 Related Work -- 1.3 Outline and Results of the Paper -- 2 Optimal Offline Algorithm -- 3 Online Algorithm for the OneAxis Model -- 4 Online Algorithms for the NoAxis Model -- 4.1 VisibleBoundary Model -- 4.2 DiscoverableBoundary Model -- 4.3 InvisibleBoundary Model -- 5 Conclusion -- References -- Space-Efficient STR-IC-LCS Computation -- 1 Introduction -- 2 Preliminaries -- 2.1 Strings -- 2.2 STR-IC-LCS -- 3 Space-efficient Solution for STR-IC-LCS Problem -- 3.1 Overview of Our Solution -- 3.2 Space-efficient Prefix LCS -- 3.3 Algorithm -- 4 Conclusions and Future Work -- References -- The k-Centre Problem for Classes of Cyclic Words -- 1 Introduction -- 2 Preliminaries -- 3 The k-centre Problem for Necklaces -- 3.1 The Overlap Distance and the k-centre Problem -- 3.2 The k-centre Problem -- 4 Approximating the k-centre Problem for necklaces -- References -- Author Index.
• Titolo autorizzato: SOFSEM 2023, theory and practice of computer science
• ISBN: 9783031231018; 9783031231001
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 9910635400403321
• Lo trovi qui: Univ. Federico II
• Serie: Lecture Notes in Computer Science