research
∙
02/22/2023
Graphs with minimum fractional domatic number
The domatic number of a graph is the maximum number of vertex disjoint d...
share
research
∙
02/17/2023
Realizing temporal graphs from fastest travel times
In this paper we initiate the study of the temporal graph realization pr...
research
∙
04/11/2022
The Complexity of Temporal Vertex Cover in Small-Degree Graphs
Temporal graphs naturally model graphs whose underlying topology changes...
research
∙
02/11/2022
The complexity of computing optimum labelings for temporal connectivity
A graph is temporally connected if there exists a strict temporal path, ...
research
∙
07/29/2021
The Complexity of Growing a Graph
Motivated by biological processes, we introduce here the model of growin...
research
∙
05/18/2021
Interference-free Walks in Time: Temporally Disjoint Paths
We investigate the computational complexity of finding temporally disjoi...
research
∙
02/12/2021
The Complexity of Transitively Orienting Temporal Graphs
In a temporal network with discrete time-labels on its edges, entities a...
research
∙
10/09/2020
Equitable Scheduling on a Single Machine
We introduce a natural but seemingly yet unstudied generalization of the...
research
∙
05/17/2020
Matching in Stochastically Evolving Graphs
This paper studies the maximum cardinality matching problem in stochasti...
research
∙
04/13/2020
Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle
In this paper we consider the following total functional problem: Given ...
research
∙
07/30/2019
Linear Programming complementation and its application to fractional graph theory
In this paper, we introduce a new kind of duality for Linear Programming...
research
∙
05/13/2019
Computing Maximum Matchings in Temporal Graphs
We study the computational complexity of finding maximum-cardinality tem...
research
∙
03/08/2019
How fast can we reach a target vertex in stochastic temporal graphs?
Temporal graphs are used to abstractly model real-life networks that are...
research
∙
11/12/2018
Sliding Window Temporal Graph Coloring
Graph coloring is one of the most famous computational problems with app...
research
∙
05/17/2018
Deleting edges to restrict the size of an epidemic in temporal networks
A variety of potentially disease-spreading contact networks can be natur...
research
∙
05/12/2018
The temporal explorer who returns to the base
In this paper we study the problem of exploring a temporal graph (i.e. a...
research
∙
05/04/2018
Lower and Upper Bound for Computing the Size of All Second Neighbourhoods
We consider the problem of computing the size of each r-neighbourhood fo...
research
∙
02/20/2018
Temporal Vertex Cover with a Sliding Time Window
Modern, inherently dynamic systems are usually characterized by a networ...
research
∙
01/15/2018
Searching for Maximum Out-Degree Vertices in Tournaments
A vertex x in a tournament T is called a king if for every vertex y of T...
research
∙
10/20/2017