Combinatorial Algorithms 33rd International Workshop, IWOCA 2022, Trier, Germany, June 7-9, 2022, Proceedings / [electronic resource] :
edited by Cristina Bazgan, Henning Fernau.
- 1st ed. 2022.
- XVIII, 524 p. 112 illus., 48 illus. in color. online resource.
- Lecture Notes in Computer Science, 13270 1611-3349 ; .
- Lecture Notes in Computer Science, 13270 .
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.
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 and randomized algorithms; and streaming algorithms.
9783031066788
10.1007/978-3-031-06678-8 doi
Computer science--Mathematics.
Discrete mathematics.
Computer engineering.
Computer networks .
Algorithms.
Data structures (Computer science).
Information theory.
Computer graphics.
Numerical analysis.
Discrete Mathematics in Computer Science.
Computer Engineering and Networks.
Design and Analysis of Algorithms.
Data Structures and Information Theory.
Computer Graphics.
Numerical Analysis.
QA76.9.M35 QA297.4
004.0151
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.
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 and randomized algorithms; and streaming algorithms.
9783031066788
10.1007/978-3-031-06678-8 doi
Computer science--Mathematics.
Discrete mathematics.
Computer engineering.
Computer networks .
Algorithms.
Data structures (Computer science).
Information theory.
Computer graphics.
Numerical analysis.
Discrete Mathematics in Computer Science.
Computer Engineering and Networks.
Design and Analysis of Algorithms.
Data Structures and Information Theory.
Computer Graphics.
Numerical Analysis.
QA76.9.M35 QA297.4
004.0151