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-19, 2023, proceedings

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-19, 2023, proceedings / Leszek Gąsieniec (ed.).

This book constitutes the conference proceedings of the 48th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2023, held in Novy Smokovec, Slovakia, during January 1518, 2023. The 22 full papers presented together with 2 best papers and 2 best students pa...

Full description

Saved in:
Bibliographic Details
Corporate Author: SOFSEM (Conference) Nový Smokovec, Slovakia)
Other Authors: Gąsieniec, Leszek (Editor)
Format: eBook
Language:English
Published: Cham : Springer, [2023]
Series:Lecture notes in computer science ; 13878.
Lecture notes in computer science. Advanced research in computing and software science.
Subjects:
Computer science > Congresses.
Computer science
proceedings (reports)
Conference papers and proceedings
Conference papers and proceedings.
Actes de congrès.
Online Access:Click for online access
Table of Contents:
  • 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

Similar Items