All Outputs (8)

Online Regenerator Placement (2011)
Presentation / Conference Contribution

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. A regenerator can serve only one ligh... Read More about Online Regenerator Placement.

Natural Models for Evolution on Networks (2011)
Presentation / Conference Contribution

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 individuals on the nodes of a network (in g... Read More about Natural Models for Evolution on Networks.

The longest path problem has a polynomial solution on interval graphs (2011)
Journal Article

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, as it is a generalization of the Hamilton... Read More about The longest path problem has a polynomial solution on interval graphs.

The recognition of tolerance and bounded tolerance graphs (2011)
Journal Article

Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. This subclass of perfect graphs has been extensively studied, due to both its interesting structure and its num... Read More about The recognition of tolerance and bounded tolerance graphs.

Computing and Counting Longest Paths on Circular-Arc Graphs in Polynomial Time (2011)
Presentation / Conference Contribution

The longest path problem asks for a path with the largest number of vertices in a given graph. The first polynomial time algorithm (with running time O(n4)) has been recently developed for interval graphs. Even though interval and circular-arc graphs... Read More about Computing and Counting Longest Paths on Circular-Arc Graphs in Polynomial Time.

Vertex Splitting and the Recognition of Trapezoid Graphs (2011)
Journal Article

Trapezoid graphs are the intersection family of trapezoids where every trapezoid has a pair of opposite sides lying on two parallel lines. These graphs have received considerable attention and lie strictly between permutation graphs (where the trapez... Read More about Vertex Splitting and the Recognition of Trapezoid Graphs.

An intersection model for multitolerance graphs: Efficient algorithms and hierarchy (2011)
Presentation / Conference Contribution

Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in con ict. This class of graphs has attracted many research eorts, mainly due to its interesting structure and its numerous... Read More about An intersection model for multitolerance graphs: Efficient algorithms and hierarchy.

The Recognition of Triangle Graphs (2011)
Presentation / Conference Contribution

Trapezoid graphs are the intersection graphs of trapezoids, where every trapezoid has a pair of opposite sides lying on two parallel lines L_{1} and L_{2} of the plane. Strictly between permutation and trapezoid graphs lie the simple-triangle graphs... Read More about The Recognition of Triangle Graphs.