-
Article
Parameterized Domination in Circle Graphs
A circle graph is the intersection graph of a set of chords in a circle. Keil [Discrete Appl. Math., 42(1):51–63, 1993] proved that Dominating Set, Connected Dominating Set, and Total Dominating Set are NP-comple...
-
Article
Approximating Fixation Probabilities in the Generalized Moran Process
We consider the Moran process, as generalized by Lieberman et al. (Nature 433:312–316, 2005). A population resides on the vertices of a finite, connected, undirected graph and, at each time step, an individual is...
-
Article
An Intersection Model for Multitolerance Graphs: Efficient Algorithms and Hierarchy
Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. This class of graphs has attracted many research efforts, mainly due t...
-
Chapter and Conference Paper
On Temporally Connected Graphs of Small Cost
We study the design of small cost temporally connected graphs, under various constraints. We mainly consider undirected graphs of n vertices, where each edge has an associated set of discrete availability instanc...
-
Reference Work Entry In depth
Multitolerance Graphs
-
Chapter and Conference Paper
Graph Editing to a Given Degree Sequence
We investigate the parameterized complexity of the graph editing problem called Editing to a Graph with a Given Degree Sequence where the aim is to obtain a graph with a given degree sequence
-
Article
Open AccessAlgorithms and Almost Tight Results for \(3\) -Colorability of Small Diameter Graphs
The \(3\) 3 ...
-
Chapter and Conference Paper
Algorithms and Complexity for Metric Dimension and Location-domination on Interval and Permutation Graphs
We study the problems Locating-Dominating Set and Metric Dimension, which consist of determining a minimum-size set of vertices that distinguishes the vertices of a graph using either neighbourhoods or distances....
-
Chapter and Conference Paper
Population Protocols for Majority in Arbitrary Networks
We study the problem of determining the majority type in an arbitrary connected network, each vertex of which has initially two possible types. The vertices may have a few additional possible states and can in...
-
Chapter and Conference Paper
When Can Graph Hyperbolicity Be Computed in Linear Time?
Hyperbolicity measures, in terms of (distance) metrics, how close a given graph is to being a tree. Due to its relevance in modeling real-world networks, hyperbolicity has seen intensive research over the last...
-
Article
Determining majority in networks with local interactions and very small local memory
We study the problem of determining the majority type in an arbitrary connected network, each vertex of which has initially two possible types. The vertices may later change into other types, out of a set of a...
-
Article
Identification, Location-Domination and Metric Dimension on Interval and Permutation Graphs. II. Algorithms and Complexity
We consider the problems of finding optimal identifying codes, (open) locating-dominating sets and resolving sets (denoted Identifying Code, (Open) Open Locating-Dominating Set and Metric Dimension) of an interva...
-
Article
Open AccessThe Complexity of Optimal Design of Temporally Connected Graphs
We study the design of small cost temporally connected graphs, under various constraints. We mainly consider undirected graphs of n vertices, where each edge has an associated set of discrete availability instanc...
-
Article
Online Regenerator Placement
Connections between nodes in optical networks are realized by lightpaths. Due to the decay of the signal, a regenerator has to be placed on every lightpath after at most d hops, for some given positive integer d....
-
Chapter and Conference Paper
Kernelization Lower Bounds for Finding Constant-Size Subgraphs
Kernelization is an important tool in parameterized algorithmics. Given an input instance accompanied by a parameter, the goal is to compute in polynomial time an equivalent instance of the same problem such t...
-
Chapter and Conference Paper
The Temporal Explorer Who Returns to the Base
In this paper we study the problem of exploring a temporal graph (i.e. a graph that changes over time), in the fundamental case where the underlying static graph is a star on n vertices. The aim of the exploratio...
-
Article
Open AccessTemporal Network Optimization Subject to Connectivity Constraints
In this work we consider temporal networks, i.e. networks defined by a labeling \(\lambda \) ...
-
Article
When Can Graph Hyperbolicity be Computed in Linear Time?
Hyperbolicity is a distance-based measure of how close a given graph is to being a tree. Due to its relevance in modeling real-world networks, hyperbolicity has seen intensive research over the last years. Unf...
-
Article
Open AccessBinary Search in Graphs Revisited
In the classical binary search in a path the aim is to detect an unknown target by asking as few queries as possible, where each query reveals the direction to the target. This binary search algorithm has been...
-
Article
Open AccessThe Power of Linear-Time Data Reduction for Maximum Matching
Finding maximum-cardinality matchings in undirected graphs is arguably one of the most central graph primitives. For m-edge and n-vertex graphs, it is well-known to be solvable in \(O(m\sqrt{n})\) O ( m n )
