Discrete Algorithms

The section covers research in all aspects of the design and analysis of discrete algorithms. This extends also to data structures, combinatorial structures, and lower bounds.


Topics includes: Algorithmic aspects of networks - Algorithmic game theory - Approximation algorithms - Combinatorial optimization - Computational biology - Distributed algorithms - Computational geometry - Data compression - Data structures - Databases and information retrieval - Graph algorithms - Hierarchical memories - Mobile computing - On-line algorithms - Parallel algorithms - Parametrized complexity - Pattern matching - Randomized algorithms - Scheduling - Streaming algorithms

Improved kernels for Signed Max Cut parameterized above lower bound on (r,l)-graphs

Faria, Luerbio ; Klein, Sulamita ; Sau, Ignasi ; Sucupira, Rubens.
A graph $G$ is signed if each edge is assigned $+$ or $-$. A signed graph is balanced if there is a bipartition of its vertex set such that an edge has sign $-$ if and only if its endpoints are in different parts. The Edwards-Erd\"os bound states that every graph with $n$ vertices and $m$ edges has […]

Pairwise Stability in Two Sided Market with Strictly Increasing Valuation Functions

Ali, Yasir ; Javaid, Asma.
This paper deals with two-sided matching market with two disjoint sets, i.e. the set of buyers and the set of sellers. Each seller can trade with at most with one buyer and vice versa. Money is transferred from sellers to buyers for an indivisible goods that buyers own. Valuation functions, for […]

Energy-optimal algorithms for computing aggregative functions in random networks

Klonowski, Marek ; Sulkowska, Małgorzata.
We investigate a family of algorithms minimizing energetic effort in random networks computing aggregative functions. In contrast to previously considered models, our results minimize maximal energetic effort over all stations instead of the average usage of energy. Such approach seems to be much […]

On the complexity of edge-colored subgraph partitioning problems in network optimization

Zhang, Xiaoyan ; Zhang, Zan-Bo ; Broersma, Hajo ; Wen, Xuelian.
Network models allow one to deal with massive data sets using some standard concepts from graph theory. Understanding and investigating the structural properties of a certain data set is a crucial task in many practical applications of network optimization. Recently, labeled network optimization […]

Reducing the rank of a matroid

Joret, Gwenaël ; Vetta, Adrian.
We consider the rank reduction problem for matroids: Given a matroid $M$ and an integer $k$, find a minimum size subset of elements of $M$ whose removal reduces the rank of $M$ by at least $k$. When $M$ is a graphical matroid this problem is the minimum $k$-cut problem, which admits a […]

Improving Vertex Cover as a Graph Parameter

Ganian, Robert.
Parameterized algorithms are often used to efficiently solve NP-hard problems on graphs. In this context, vertex cover is used as a powerful parameter for dealing with graph problems which are hard to solve even when parameterized by tree-width; however, the drawback of vertex cover is that bounding […]

On substitution tilings of the plane with n-fold rotational symmetry

Maloney, Gregory R..
A method is described for constructing, with computer assistance, planar substitution tilings that have n-fold rotational symmetry. This method uses as prototiles the set of rhombs with angles that are integer multiples of pi/n, and includes various special cases that have already been constructed […]

Output sensitive algorithms for covering many points

Ghasemalizadeh, Hossein ; Razzazi, Mohammadreza.
In this paper we devise some output sensitive algorithms for a problem where a set of points and a positive integer, m, are given and the goal is to cover a maximal number of these points with m disks. We introduce a parameter, ρ, as the maximum number of points that one disk can cover and we […]

Cost-effectiveness of algorithms

Farr, Graham.
In this paper we discuss how to assess the performance of algorithms for optimisation problems in a way that balances solution quality and time. We propose measures of cost-effectiveness for such algorithms. These measures give the gain in solution quality per time unit over a sequence of inputs, […]

A randomized algorithm for finding a maximum clique in the visibility graph of a simple polygon

Cabello, Sergio ; Saumell, Maria.
We present a randomized algorithm to compute a clique of maximum size in the visibility graph G of the vertices of a simple polygon P. The input of the problem consists of the visibility graph G, a Hamiltonian cycle describing the boundary of P, and a parameter δ∈(0,1) controlling the probability of […]

Determining pure discrete spectrum for some self-affine tilings

Akiyama, Shigeki ; Gähler, Franz ; Lee, Jeong-Yup.
By the algorithm implemented in the paper by Akiyama-Lee [Adv. Math. 226(4):2855 13;2883, 2011] and some of its predecessors, we have examined the pure discreteness of the spectrum for all irreducible Pisot substitutions of trace less than or equal to 2, and some cases of planar tilings generated by […]

An exact algorithm for the generalized list T-coloring problem

Junosza-Szaniawski, Konstanty ; Rzazewski, Pawel.
The generalized list T-coloring is a common generalization of many graph coloring models, including classical coloring, L(p,q)-labeling, channel assignment and T-coloring. Every vertex from the input graph has a list of permitted labels. Moreover, every edge has a set of forbidden differences. We […]

A Parameterized Measure-and-ConquerAnalysis for Finding a k-Leaf Spanning Treein an Undirected Graph

Binkele-Raible, Daniel ; Fernau, Henning.
The problem of finding a spanning tree in an undirected graph with a maximum number of leaves is known to be NP-hard. We present an algorithm which finds a spanning tree with at least k leaves in time O*(3.4575k) which improves the currently best algorithm. The estimation of the running time is done […]

The Price of Mediation

Bradonjic, Milan ; Ercal, Gunes ; Meyerson, Adam ; Roytman, Alan.
We study the relationship between correlated equilibria and Nash equilibria. In contrast to previous work focusing on the possible benefits of a benevolent mediator, we define and bound the Price of Mediation (PoM): the ratio of the social cost (or utility) of the worst correlated equilibrium to the […]

A note on contracting claw-free graphs

Fiala, Jiří ; Kamiński, Marcin ; Paulusma, Daniël.
A graph containment problem is to decide whether one graph called the host graph can be modified into some other graph called the target graph by using a number of specified graph operations. We consider edge deletions, edge contractions, vertex deletions and vertex dissolutions as possible graph […]

The complexity of 2-coloring and strong coloring in uniform hypergraphs of high minimum degree

Szymańska, Edyta.
In this paper we consider the problem of deciding whether a given r-uniform hypergraph H with minimum vertex degree at least c\binom|V(H)|-1r-1, or minimum degree of a pair of vertices at least c\binom|V(H)|-2r-2, has a vertex 2-coloring. Motivated by an old result of Edwards for graphs, we obtain […]

Efficient repeat finding in sets of strings via suffix arrays

Barenbaum, Pablo ; Becher, Verónica ; Deymonnaz, Alejandro ; Halsband, Melisa ; Heiber, Pablo Ariel.
We consider two repeat finding problems relative to sets of strings: (a) Find the largest substrings that occur in every string of a given set; (b) Find the maximal repeats in a given string that occur in no string of a given set. Our solutions are based on the suffix array construction, requiring […]

Isomorphism of graph classes related to the circular-ones property

Curtis, Andrew R. ; Lin, Min Chih ; Mcconnell, Ross M. ; Nussbaum, Yahav ; Soulignac, Francisco Juan ; Spinrad, Jeremy P. ; Szwarcfiter, Jayme Luiz.
We give a linear-time algorithm that checks for isomorphism between two 0-1 matrices that obey the circular-ones property. Our algorithm is similar to the isomorphism algorithm for interval graphs of Lueker and Booth, but works on PC trees, which are unrooted and have a cyclic nature, rather than […]

On quadratic threshold CSPs

Austrin, Per ; Benabbas, Siavosh ; Magen, Avner.
A predicate P: {-1, 1}k →{0, 1} can be associated with a constraint satisfaction problem Max CSP(P). P is called ''approximation resistant'' if Max CSP(P) cannot be approximated better than the approximation obtained by choosing a random assignment, and ''approximable'' otherwise. This […]

A linear time algorithm for finding an Euler walk in a strongly connected 3-uniform hypergraph

Lonc, Zbigniew ; Naroski, Pawel.
By an Euler walk in a 3-uniform hypergraph H we mean an alternating sequence v(0), epsilon(1), v(1), epsilon(2), v(2), ... , v(m-1), epsilon(m), v(m) of vertices and edges in H such that each edge of H appears in this sequence exactly once and v(i-1); v(i) is an element of epsilon(i), v(i-1) not […]

Generation of Cubic graphs

Brinkmann, Gunnar ; Goedgebeur, Jan ; Mckay, Brendan D..
We describe a new algorithm for the efficient generation of all non-isomorphic connected cubic graphs. Our implementation of this algorithm is more than 4 times faster than previous generators. The generation can also be efficiently restricted to cubic graphs with girth at least 4 or 5.