Computing and Combinatorics : 27th International Conference, COCOON 2021, Tainan, Taiwan, October 24-26, 2021, Proceedings / edited by Chi-Yeh Chen, Wing-Kai Hon, Ling-Ju Hung, Chia-Wei Lee.

Format:

Book

Contributor:

Chen, Chi-Yeh, Editor.

Hon, Wing-Kai., Editor.

Hung, Ling-Ju, Editor.

Lee, Chia-Wei, Editor.

SpringerLink (Online service)

Series:

Computer Science (SpringerNature-11645)

LNCS sublibrary. Theoretical computer science and general issues 2512-2029 ; SL 1, 13025

Theoretical Computer Science and General Issues, 2512-2029 ; 13025

Language:

English

Subjects (All):

Computer science.

Data structures (Computer science).

Information theory.

Computer science-Mathematics.

Algorithms.

Theory of Computation.

Data Structures and Information Theory.

Mathematics of Computing.

Local Subjects:

Theory of Computation.

Data Structures and Information Theory.

Mathematics of Computing.

Algorithms.

Physical Description:

1 online resource (XXI, 694 pages) : 173 illustrations, 67 illustrations in color.

Edition:

1st ed. 2021.

Contained In:

Springer Nature eBook

Place of Publication:

Cham : Springer International Publishing : Imprint: Springer, 2021.

System Details:

text file PDF

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.

Contents:

Algorithms

Limitations of the Impagliazzo-Nisan-Wigderson Pseudorandom Generator against Permutation Branching Programs

All-to-All Broadcast in Dragonfly Networks

An Efficient Algorithm for Enumerating Longest Common Increasing Subsequences

On Singleton Congestion Games with Resilience Against Collusion

A Pivot Gray Code Listing for the Spanning Trees of the Fan Graph

Approximation Algorithms

General Max-Min Fair Allocation

On the approximation hardness of geodetic set and its variants

Approximate Distance Oracles with Improved Stretch for Sparse Graphs

Hardness and Approximation Results of Roman \{3\}-Domination in Graphs

Approximation algorithms for priority Steiner tree problems

Sublinear-Space Approximation Algorithms for Max r-SAT

A Further Improvement on Approximating TTP-2

Automata

Sequence graphs realizations and ambiguity in language models

Between SC and LOGDCFL: Families of Languages Accepted by Polynomial-Time Logarithmic-Space Deterministic Auxiliary Depth-k Storage Automata

Ideal Separation and General Theorems for Constrained Synchronization and their Application to Small Constraint Automata

Most Pseudo-copy Languages Are Not Context-free

Computational Geometry

Bottleneck Convex Subsets: Finding k Large Convex Sets in a Point Set

Deterministic metric 1-median selection with a 1 - o(1) fraction of points ignored

The Coverage problem by Aligned Disks

Consistent Simplification of Polyline Tree Bundles

Improving Upper and Lower Bounds for the Total Number of Edge Crossings of Euclidean Minimum Weight Laman Graphs

Minimum Color Spanning Circle in Imprecise Setup

Fault Tolerant Computing and Fault Diagnosis

Reliability Evaluation of Subsystem Based on Exchanged Hypercube

Fault diagnosability of regular networks under the Hybrid PMC model

A Study for Conditional Diagnosability of Pancake Graphs

A new measure for locally t-diagnosable under PMC model

Graph Algorithms

Colouring graphs with no induced six-vertex path or diamond

Constructing Tri-CISTs in Shu e-Cubes

Reconfiguring Directed Trees in a Digraph

Decremental Optimization of Vertex-Coloring Under the Reconfiguration Framework

Embedding Three Edge-disjoint Hamiltonian Cycles into Locally Twisted Cubes

On the Probe Problem for (r,l)-Well-Coveredness

Distinguishing graphs via cycles

Graph Theory and Applications

The Restrained Domination and Independent Restrained Domination in Extending Supergrid Graphs

The Concentration of the Maximum Degree in the Duplication-Divergence Models

Conditional Fractional Matching Preclusion for Burnt Pancake Graphs and Pancake-Like Graphs

The Weakly Dimension-balanced Pancyclicity on Toroidal Mesh Graph Tm,n when Both m and n Are Odd

Hypercontractivity via Tensor Calculus

Network and Algorithms

Respecting Lower Bounds in Uniform Lower and Upper Bounded Facility Location Problem

Finding Cheapest Deadline Paths

Approximate the Lower-Bounded Connected Facility Location Problem

Mechanism Design for Facility Location with Fractional Preferences and Minimum Distance

Online Algorithm and Streaming Algorithms

On the Hardness of Opinion Dynamics Optimization with L1-Budget on Varying Susceptibility to Persuasion

Symmetric Norm Estimation and Regression on Sliding Windows

Single-Pass Streaming Algorithms to Partition Graphs into Few Forests

The Secretary Problem with Reservation Costs

Online Ride-Hitching in UAV Travelling

Parameterized Complexity and Algorithms Disconnected Matchings

On the d-Claw Vertex Deletion Problem

Constrained Hitting Set Problem with Intervals

Exact algorithms for maximum weighted independent set on sparse graphs

Recreational Games

Two Standard Decks of Playing Cards are Sufficient for a ZKP for Sudoku

Token Shifting on Graphs

Computational Complexity of Jumping Block Puzzles

A Card-minimal Three-Input AND Protocol Using Two Shuffles

Spy game: FPT-algorithm and results on graph products

.

Other Format:

Printed edition:

ISBN:

978-3-030-89543-3

9783030895433

Access Restriction:

Restricted for use by site license.