Combinatorial Algorithms

33rd International Workshop, IWOCA 2022, Trier, Germany, June 7–9, 2022, Proceedings

Cristina Bazgan, Henning Fernau (Herausgeber)

Buch | Softcover

XVIII, 524 Seiten

2022 | 1st ed. 2022
Springer International Publishing (Verlag)
978-3-031-06677-1 (ISBN)

Artikel merken

This book constitutes the refereed proceedings of the 33rd International Workshop on Combinatorial Algorithms, IWOCA 2022, which took place as a hybrid event in Trier, Germany, during June 7-9, 2022.The 35 papers presented in these proceedings were carefully reviewed and selected from 86 submissions. They deal with diverse topics related to combinatorial algorithms, such as algorithms and data structures; algorithmic and combinatorical aspects of cryptography and information security; algorithmic game theory and complexity of games; approximation algorithms; complexity theory; combinatorics and graph theory; combinatorial generation, enumeration and counting; combinatorial optimization; combinatorics of words; computational biology; computational geometry; decompositions and combinatorial designs; distributed and network algorithms; experimental combinatorics; fine-grained complexity; graph algorithms and modelling with graphs; graph drawingand graph labelling; network theory and temporal graphs; quantum computing and algorithms for quantum computers; online algorithms; parameterized and exact algorithms; probabilistic andrandomized algorithms; and streaming algorithms.

Distance from Triviality 2.0: Hybrid Parameterizations.- Graphs as Algorithms: Characterizing Motion-Planning Gadgets through Simulation and Complexity.- On the Existence of EFX Allocations.- Lower Bounds for Restricted Schemes in the Two-Adaptive Bitprobe Model.- Perfect Matchings with Crossings.- Graph parameters, implicit representations and factorial properties.- Approximating Subset Sum Ratio via Subset Sum Computations.- Faster Algorithm for Finding Maximum 1-Restricted Simple 2-Matchings.- Lower bounds on the performance of online algorithms for relaxed packing problems.- An Adjacency Labeling Scheme Based On A Decomposition Of Trees Into Caterpillars.- Computing Longest (Common) Lyndon Subsequence.- Structure-aware combinatorial group testing: a new method for pandemic screening.- Convex Grid Drawings of Planar Graphs with Constant Edge-Vertex Resolution.- 1-Extendability of independent sets.- Tukey Depth Histograms.- An Efficient Algorithm for the Proximity Connected Two Center Problem.- A New Temporal Interpretation of Cluster Editing.- List covering of regular multigraphs.- The Slotted Online One-Sided Crossing Minimization Problem on 2-Regular Graphs.- Perfect matching cuts partitioning a graph into complementary subgraphs.- On the Intractability Landscape of Digraph Intersection Representations.- The Red-Blue Separation problem on graphs.- Harmless Sets in Sparse Classes.- The Parameterized Complexity of s-Club with Triangle and Seed Constraints.- Space-Efficient B Trees via Load-Balancing.- An Additive Approximation Scheme for the Nash Social Welfare Maximization with Identical Additive Valuations.- Controlling Weighted Voting Games by Deleting or Adding Players with or without Changing the Quota.- Practical Space-Efficient Index for Structural Pattern Matching.- A Shift Gray Code for Fixed-Content Lukasiewicz Words.- Learning from Positive and Negative Examples: Dichotomies and Parameterized Algorithms.- Using Edge Contractions and Vertex Deletions toReduce the Independence Number and the Clique Number.- Shortest Unique Palindromic Substring Queries in Semi-dynamic Settings.- On relative clique number of triangle-free planar colored mixed graphs..- Exact Polynomial Time Algorithm for the Response Time Analysis of Harmonic Tasks.- Computing a Minimum Subset Feedback Vertex Set on Chordal Graphs Parameterized by Leafage.- Linear Time Construction of Indexable Elastic Founder Graphs.- On Critical Node Problems with Vulnerable Vertices.- Winner Determination Algorithms for Graph Games with Matching Structures.

Erscheinungsdatum	24.05.2022
Reihe/Serie	Lecture Notes in Computer Science
Zusatzinfo	XVIII, 524 p. 112 illus., 48 illus. in color.
Verlagsort	Cham
Sprache	englisch
Maße	155 x 235 mm
Gewicht	825 g
Themenwelt	Mathematik / Informatik ► Informatik ► Netzwerke
	Informatik ► Theorie / Studium ► Algorithmen
	Mathematik / Informatik ► Mathematik
Schlagworte	Applications • approximation algorithms analysis • combinatorics • Complexity Classes • Computer Networks • Computer Science • computer vision • conference proceedings • data structure design and analysis • Directed graphs • Discrete Mathematics • graph algorithms analysis • Graphic methods • graph theory • Informatics • Mathematical Optimization • Mathematics • polynomial approximation • problems, reductions and completeness • Research • Signal Processing • Theory of Computation • weighted graph
ISBN-10	3-031-06677-4 / 3031066774
ISBN-13	978-3-031-06677-1 / 9783031066771
Zustand	Neuware