19 Result(s)
within
George B. Mertzios
Discrete Mathematics in Computer Science
-
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...
-
Chapter and Conference Paper
On the Intersection of Tolerance and Cocomparability Graphs
It has been conjectured by Golumbic and Monma in 1984 that the intersection of tolerance and cocomparability graphs coincides with bounded tolerance graphs. Since cocomparability graphs can be efficiently reco...
-
Chapter and Conference Paper
Natural Models for Evolution on Networks
Evolutionary dynamics have been traditionally studied in the context of homogeneous populations, mainly described by the Moran process [15]. Recently, this approach has been generalized in [13] by arranging in...
-
Chapter and Conference Paper
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
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...
-
Chapter and Conference Paper
The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders Is Polynomial
Intersection graphs of geometric objects have been extensively studied, both due to their interesting structure and their numerous applications; prominent examples include interval graphs and permutation graph...
-
Chapter and Conference Paper
Temporal Network Optimization Subject to Connectivity Constraints
In this work we consider temporal networks, i.e. networks defined by a labeling λ assigning to each edge of an underlying graph G a set of discrete time-labels. The labels of an ed...
-
Chapter and Conference Paper
On the Recognition of Four-Directional Orthogonal Ray Graphs
Orthogonal ray graphs are the intersection graphs of horizontal and vertical rays (i.e. half-lines) in the plane. If the rays can have any possible orientation (left/right/up/down) then the graph is a 4-direction...
-
Chapter and Conference Paper
Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs
The 3-coloring problem is well known to be NP-complete. It is also well known that it remains NP-complete when the input is restricted to graphs with diameter 4. Moreover, assuming the Exponential Time Hypothe...
-
Chapter and Conference Paper
Strong Bounds for Evolution in Networks
This work extends what is known so far for a basic model of evolutionary antagonism in undirected networks (graphs). More specifically, this work studies the generalized Moran process, as introduced by Lieberm...
-
Chapter and Conference Paper
Minimum Bisection Is NP-hard on Unit Disk Graphs
In this paper we prove that the Min-Bisection problem is NP-hard on unit disk graphs, thus solving a longstanding open question.
-
Chapter and Conference Paper
Intersection Graphs of L-Shapes and Segments in the Plane
An L-shape is the union of a horizontal and a vertical segment with a common endpoint. These come in four rotations: $\lfloor, \lceil,...
-
Chapter and Conference Paper
Determining Majority in Networks with Local Interactions and Very Small Local Memory
We study here the problem of determining the majority type in an arbitrary connected network, each vertex of which has initially two possible types (states). The vertices may have a few additional possible sta...
-
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...
-
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
-
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
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...
-
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...
-
Chapter and Conference Paper
Payment Scheduling in the Interval Debt Model
The networks-based study of financial systems has received considerable attention in recent years, but seldom explicitly incorporated the dynamic aspects of such systems. We consider this problem setting from ...
