| Description |
1 online resource (699 pages) |
| Series |
Lecture notes in computer science ; 13025 |
|
LNCS sublibrary, SL 1, Theoretical computer science and general issues |
|
Lecture notes in computer science ; 13025.
|
|
LNCS sublibrary. SL 1, Theoretical computer science and general issues.
|
| Contents |
Intro -- Preface -- Organization -- Abstracts of Invited Talks -- Coupon Allocation in Social Market: Robust and Machine Learning -- Discrepancy Theory in Combinatorics, Geometry and Computation -- Learning Graphs with Topology Properties -- Bamboo Garden Trimming Problem -- Contents -- Algorithms -- Limitations of the Impagliazzo-Nisan-Wigderson Pseudorandom Generator Against Permutation Branching Programs -- 1 Introduction -- 1.1 Pseudorandom Generators for Space-Bounded Computation -- 1.2 Permutation Branching Programs -- 1.3 Our Results -- 1.4 Techniques -- References |
|
All-to-All Broadcast in Dragonfly Networks -- 1 Introduction -- 2 Preliminaries -- 3 All-to-All Broadcast Using One-to-All Broadcast Schemes -- 4 The Proposed All-to-All Broadcast Algorithm A2A -- 5 Conclusions -- References -- An Efficient Algorithm for Enumerating Longest Common Increasing Subsequences -- 1 Introduction -- 2 The Proposed Algorithm -- 2.1 Assumptions -- 2.2 Algorithm Overview -- 2.3 Detailed Description -- 2.4 Example -- 3 The Analysis -- 3.1 Correctness -- 3.2 Complexity -- 4 Conclusion and Discussion -- References |
|
On Singleton Congestion Games with Resilience Against Collusion -- 1 Introduction -- 2 The Model and the Preliminaries -- 3 The Main Result -- References -- A Pivot Gray Code Listing for the Spanning Trees of the Fan Graph -- 1 Introduction -- 1.1 New Results -- 2 A Greedy Generation for Tn -- 3 An O(1)-Amortized Time Pivot Gray Code Generation for Tn -- 3.1 Ranking and Unranking -- 4 Conclusion -- References -- Approximation Algorithms -- General Max-Min Fair Allocation -- 1 Introduction -- 2 Every Resource Has a Positive Utility for Every Player |
|
3 Some Resources Have Zero Utility for Some Players -- 3.1 Resources and Over-Estimation -- 3.2 Fat Edges and Thin Edges -- 3.3 Overview of the Algorithm -- 3.4 Layers of Addable and Blocking Edges -- 3.5 The Local Search Step -- 3.6 Analysis -- 4 Conclusion -- References -- On the Approximation Hardness of Geodetic Set and Its Variants -- 1 Introduction -- 2 Notations -- 3 Hardness to Find a Geodesic Assignation -- 4 Approximation -- 5 Reduction from Set Cover -- 5.1 On General Case -- 5.2 On Subcubic Bipartite Graphs -- 6 Non-approximability |
|
6.1 Strong Geodetic Set and Strong Edge Geodetic Set -- 6.2 Geodetic Set and Edge Geodetic Set -- 7 Strong Geodetic Number on Complete Multipartite Graphs -- 8 Conclusion -- References -- Approximate Distance Oracles with Improved Stretch for Sparse Graphs -- 1 Introduction -- 1.1 Related Work -- 1.2 Paper Organization -- 2 Preliminaries and Previous Work -- 2.1 The Distance Oracle of Thorup and Zwick -- 2.2 A Standard Variant of the Distance Oracle of Thorup and Zwick -- 3 Distance Oracles with Improved Stretch -- 4 A Refined Stretch Analysis of Thorup-Zwick Distance Oracle |
| Summary |
This book constitutes the proceedings of the 27th International Conference on Computing and Combinatorics, COCOON 2021, held in Tainan, Taiwan, in October 2021. Due to the COVID-19 pandemic, COCOON 2021 was organized as a hybrid conference. The 56 papers presented in this volume were carefully reviewed and selected from 131 submissions. The papers are divided into the following topical sub-headings: algorithms, approximation algorithms, automata, computational geometry, fault tolerant computing and fault diagnosis, graph algorithms, graph theory and applications, network and algorithms, online algorithm and stream algorithms, parameterized complexity and algorithms, and recreational games |
| Notes |
5 Concluding Remarks |
|
Includes author index |
|
Online resource; title from PDF title page (SpringerLink, viewed November 3, 2021) |
| Subject |
Combinatorial analysis -- Data processing -- Congresses
|
|
Computer science -- Congresses
|
|
Combinatorial analysis -- Data processing
|
|
Computer science
|
| Genre/Form |
Electronic books
|
|
proceedings (reports)
|
|
Conference papers and proceedings
|
|
Conference papers and proceedings.
|
|
Actes de congrès.
|
| Form |
Electronic book
|
| Author |
Chen, Chi-Yeh
|
|
Hon, Wing-Kai
|
|
Hung, Ling-Ju
|
|
Lee, Chia-Wei
|
| ISBN |
9783030895433 |
|
3030895432 |
|
