Combinatorial Algorithms
33rd International Workshop, IWOCA 2022, Trier, Germany, June 7–9, 2022, Proceedings
Page
%P
-
Article
Preface of the Special Issue Dedicated to Selected Papers from IWOCA 2022
-
Article
Open AccessApproximating multiobjective optimization problems: How exact can you be?
It is well known that, under very weak assumptions, multiobjective optimization problems admit \((1+\varepsilon ,\dots ,1+\varepsilon )\) ...
-
Article
An approximation algorithm for the maximum spectral subgraph problem
Modifying the topology of a network to mitigate the spread of an epidemic with epidemiological constant \(\lambda \) ...
-
Article
Open AccessAn approximation algorithm for a general class of parametric optimization problems
In a (linear) parametric optimization problem, the objective value of each feasible solution is an affine function of a real-valued parameter and one is interested in computing a solution for each possible val...
-
Article
Open AccessThe Power of the Weighted Sum Scalarization for Approximating Multiobjective Optimization Problems
We determine the power of the weighted sum scalarization with respect to the computation of approximations for general multiobjective minimization and maximization problems. Additionally, we introduce a new mu...
-
Book and Conference Proceedings
-
Article
Open AccessOne-exact approximate Pareto sets
Papadimitriou and Yannakakis (Proceedings of the 41st annual IEEE symposium on the Foundations of Computer Science (FOCS), pp 86–92, 2000) show that the polynomial-time solvability of a certain auxiliary probl...
-
Chapter and Conference Paper
Monte Carlo Search Algorithms for Network Traffic Engineering
The aim of Traffic Engineering is to provide routing configurations in networks such that the used resources are minimized while maintaining a high level of quality of service (QoS). Among the optimization pro...
-
Chapter and Conference Paper
How to Get a Degree-Anonymous Graph Using Minimum Number of Edge Rotations
A graph is k-degree-anonymous if for each vertex there are at least \(k-1 \) k - 1 other vertices of the same degree in the graph. Min Anonymous-Edge-Rotation asks for a given graph G and a positive integer...
-
Chapter and Conference Paper
Parameterized Dynamic Variants of Red-Blue Dominating Set
We introduce a parameterized dynamic version of the Red-Blue Dominating Set problem and its partial version. We prove the fixed-parameter tractability of the dynamic versions with respect to the (so called) e...
-
Chapter and Conference Paper
An FPTAS for a General Class of Parametric Optimization Problems
In a (linear) parametric optimization problem, the objective value...
-
Article
Clustering with Lower-Bounded Sizes
Classical clustering problems search for a partition of objects into a fixed number of clusters. In many scenarios, however, the number of clusters is not known or necessarily fixed. Further, clusters are some...
-
Article
Open AccessStructural and Algorithmic Properties of 2-Community Structures
We investigate the structural and algorithmic properties of 2-community structures in graphs introduced recently by Olsen (Math Soc Sci 66(3):331–336, 2013). A 2-community structure is a partition of a vertex set...
-
Chapter and Conference Paper
Relaxation and Matrix Randomized Rounding for the Maximum Spectral Subgraph Problem
Modifying the topology of a network to mitigate the spread of an epidemic with epidemiological constant \(\lambda \) ...
-
Chapter and Conference Paper
On the Complexity of Finding a Potential Community
An independent 2-clique of a graph is a subset of vertices that is an independent set and such that any two vertices inside have a common neighbor outside. In this paper, we study the complexity of finding an ...
-
Chapter and Conference Paper
On the Approximability of Partial VC Dimension
We introduce the problem Partial VC Dimension that asks, given a hypergraph \(H=(X,E)\) and integers k and
-
Chapter and Conference Paper
Algorithmic Aspects of Upper Domination: A Parameterised Perspective
This paper studies Upper Domination, i.e., the problem of computing the maximum cardinality of a minimal dominating set in a graph, with a focus on parameterised complexity. Our main results include W[1]-hardness...
-
Chapter and Conference Paper
On the Complexity Landscape of the Domination Chain
In this paper, we survey and supplement the complexity landscape of the domination chain parameters as a whole, including classifications according to approximability and parameterised complexity. Moreover, we...
-
Chapter and Conference Paper
Upper Domination: Complexity and Approximation
We consider Upper Domination, the problem of finding a maximum cardinality minimal dominating set in a graph. We show that this problem does not admit an
-
Chapter and Conference Paper
On the Complexity of QoS-Aware Service Selection Problem
This paper addresses the QoS-aware service selection problem considering complex workflow patterns. More specifically, it focuses on the complexity issues of the problem. The
