-
Chapter and Conference Paper
The Longest Path Problem Is Polynomial 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...
-
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
Placing Regenerators in Optical Networks to Satisfy Multiple Sets of Requests
The placement of regenerators in optical networks has become an active area of research during the last years. Given a set of lightpaths in a network G and a positive integer d, regenerators must be placed in suc...
-
Article
Preemptive Scheduling of Equal-Length Jobs in Polynomial Time
We study the preemptive scheduling problem of a set of n jobs with release times and equal processing times on a single machine. The objective is to minimize the sum of the weighted completion times ...
-
Article
An Optimal Algorithm for the k-Fixed-Endpoint Path Cover on Proper Interval Graphs
In this paper we consider the k-fixed-endpoint path cover problem on proper interval graphs, which is a generalization of the path cover problem. Given a graph G and a set T of k vertices, a k-fixed-endpoint path...
-
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....
-
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
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...
-
Living Reference Work Entry In depth
Multitolerance Graphs
-
Living Reference Work Entry In depth
Approximating Fixation Probabilities in the Generalized Moran Process
-
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...
