-
Article
Open AccessAlgorithms and Almost Tight Results for \(3\) -Colorability of Small Diameter Graphs
The \(3\) 3 ...
-
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
Open AccessTemporal Network Optimization Subject to Connectivity Constraints
In this work we consider temporal networks, i.e. networks defined by a labeling \(\lambda \) ...
-
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 )
-
Article
Open AccessApproximate and Randomized Algorithms for Computing a Second Hamiltonian Cycle
In this paper we consider the following problem: Given a Hamiltonian graph G, and a Hamiltonian cycle C of G, can we compute a second Hamiltonian cycle ...
