Outputs (125)

An optimal algorithm for the k-fixed-endpoint path cover on proper interval graphs (2010)
Journal Article
Mertzios, G., & Unger, W. (2010). An optimal algorithm for the k-fixed-endpoint path cover on proper interval graphs. Mathematics in Computer Science, 3(1), 85-96. https://doi.org/10.1007/s11786-009-0004-y

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 cover of G with respect to T is a set... Read More about An optimal algorithm for the k-fixed-endpoint path cover on proper interval graphs.

Preemptive scheduling of equal-length jobs in polynomial time (2010)
Journal Article
Mertzios, G., & Unger, W. (2010). Preemptive scheduling of equal-length jobs in polynomial time. Mathematics in Computer Science, 3(1), 73-84. https://doi.org/10.1007/s11786-009-0003-z

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 åi=1nwiCini=1wiCi of the jobs. We propose for this... Read More about Preemptive scheduling of equal-length jobs in polynomial time.

The Recognition of Tolerance and Bounded Tolerance Graphs (2010)
Presentation / Conference Contribution
Mertzios, G., Sau, I., Zaks, S., Marion, J.-Y., & Schwentick, T. (2010, March). The Recognition of Tolerance and Bounded Tolerance Graphs. Presented at 27th International Symposium on Theoretical Aspects of Computer Science (STACS), Nancy, France

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.

A New Intersection Model and Improved Algorithms for Tolerance Graphs (2009)
Journal Article
Mertzios, G., Sau, I., & Zaks, S. (2010). A New Intersection Model and Improved Algorithms for Tolerance Graphs. SIAM Journal on Discrete Mathematics, 23(4), 1800-1813. https://doi.org/10.1137/09075994x

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 and permutation graphs, has attracted ma... Read More about A New Intersection Model and Improved Algorithms for Tolerance Graphs.

New PDE-based methods for image enhancement using SOM and Bayesian inference in various discretization schemes (2009)
Journal Article
Karras, D., & Mertzios, G. (2009). New PDE-based methods for image enhancement using SOM and Bayesian inference in various discretization schemes. Measurement Science and Technology, 20(10), Article 104012. https://doi.org/10.1088/0957-0233/20/10/104012

A novel approach is presented in this paper for improving anisotropic diffusion PDE models, based on the Perona–Malik equation. A solution is proposed from an engineering perspective to adaptively estimate the parameters of the regularizing function... Read More about New PDE-based methods for image enhancement using SOM and Bayesian inference in various discretization schemes.

The longest path problem is polynomial on interval graphs (2009)
Presentation / Conference Contribution
Ioannidou, K., Mertzios, G., & Nikolopoulos, S. (2009, August). The longest path problem is polynomial on interval graphs. Presented at 34st International Symposium on Mathematical Foundations of Computer Science (MFCS), Novy Smokovec, Slovakia

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 is polynomial on interval graphs.

A parameterized algorithm for the preemptive scheduling of equal-length jobs (2009)
Presentation / Conference Contribution
Mertzios, G., & Unger, W. (2009, July). A parameterized algorithm for the preemptive scheduling of equal-length jobs. Presented at International Conference on Theoretical and Mathematical Foundations of Computer Science (TMFCS-09), Orlando, Florida

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 n i=1 wiCi of the jobs. We propose for this problem... Read More about A parameterized algorithm for the preemptive scheduling of equal-length jobs.

Fast convergence of routing games with splittable flows (2009)
Presentation / Conference Contribution
Mertzios, G. (2009, July). Fast convergence of routing games with splittable flows. Presented at International Conference on Theoretical and Mathematical Foundations of Computer Science (TMFCS- 09), Orlando, Florida

In this paper we investigate the splittable routing game in a series-parallel network with two selfish players. Every player wishes to route optimally, i.e. at minimum cost, an individual flow demand from the source to the destination, giving rise to... Read More about Fast convergence of routing games with splittable flows.

A matrix characterization of interval and proper interval graphs (2008)
Journal Article
Mertzios, G. (2008). A matrix characterization of interval and proper interval graphs. Applied Mathematics Letters, 21(4), 332-337. https://doi.org/10.1016/j.aml.2007.04.001

In this work a matrix representation that characterizes the interval and proper interval graphs is presented, which is useful for the efficient formulation and solution of optimization problems, such as the k-cluster problem. For the construction of... Read More about A matrix characterization of interval and proper interval graphs.

The friendship problem on graphs (2008)
Presentation / Conference Contribution
Mertzios, G., & Unger, W. (2008, May). The friendship problem on graphs. Presented at 1st International Conference on Relations, Orders and Graphs : Interaction with Computer Science (ROGICS), Mahdia, Tunisia