14 Result(s)
within
George B. Mertzios
Algorithms
-
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 ...
-
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
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 AccessTemporal Network Optimization Subject to Connectivity Constraints
In this work we consider temporal networks, i.e. networks defined by a labeling \(\lambda \) ...
-
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 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
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...
-
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...
-
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...
-
Chapter and Conference Paper
Parameterized Domination in Circle Graphs
A circle graph is the intersection graph of a set of chords in a circle. Keil [Discrete Applied Mathematics, 42(1):51-63, 1993] proved that Dominating Set, Connected Dominating Set, and Total Dominating Set are N...
-
Article
The Longest Path Problem has a Polynomial Solution on Interval Graphs
The longest path problem is the problem of finding a path of maximum length in a graph. Polynomial solutions for this problem are known only for small classes of graphs, while it is NP-hard on general graphs, ...
-
Chapter and Conference Paper
A New Intersection Model and Improved Algorithms for Tolerance Graphs
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, which generalizes in a natural way both interval...
