The traveling salesman problem is one of the most important problems in operations research, especially when additional precedence constraints are considered. Here, we consider the well-known variant where a linear order on k special vertices is given that has to be preserved in any feasible Hamiltonian cycle. This problem is called Ordered TSP and we consider it on input instances where the edge-cost function satisfies a β-relaxed triangle inequality, i.e., where the length of a direct edge cannot exceed the cost of any detour via a third vertex by more than a factor of β> 1. We design two new polynomial-time approximation algorithms for this problem. The first algorithm essentially improves over the best previously known algorithm for almost all values of k and β< 1.087889. The second algorithm gives a further improvement for 2n ≥ 11k + 7 and β< √34/3 , where n is the number of vertices in the graph.

A Hamming compatible metric is an integer-valued metric on the words of a finite alphabet which agrees with the usual Hamming distance for words of equal length. We define a new Hamming compatible metric and show this metric is minimal in the class of all “well-behaved” Hamming compatible metrics. This gives a negative answer to a question stated by Echi in his paper [O. Echi, Appl. Math. Sci. (Ruse) 3 (2009) 813–824.].

We present a new model of a two-dimensional computing device called Sgraffito automaton. In general, the model is quite simple, which allows a clear design of computations. When restricted to one-dimensional inputs, that is, strings, the Sgraffito automaton does not exceed the power of finite-state automata. On the other hand, for two-dimensional inputs, it yields a family of picture languages with good closure properties that strictly includes the class REC  of recognizable picture languages. The deterministic Sgraffito automata define a class of picture languages that includes the class of deterministic recognizable picture languages DREC, the class of picture languages that are accepted by four-way alternating automata, those that are accepted by deterministic one-marker automata, and the sudoku-deterministically recognizable picture languages, but the membership problem for the accepted languages is still decidable in polynomial time. In addition, the deterministic Sgraffito automata accept some unary picture languages that are outside of the class REC.

The minimum roman dominating problem (denoted by γR(G), the weight of minimum roman dominating function of graph G) is a variant of the very well known minimum dominating set problem (denoted by γ(G), the cardinality of minimum dominating set of graph G). Both problems remain NP-Complete when restricted to P5-free graph class [A.A. Bertossi, Inf. Process. Lett. 19 (1984) 37–40; E.J. Cockayne, et al. Discret. Math. 278 (2004) 11–22]. In this paper we study both problems restricted to some subclasses of P5-free graphs. We describe robust algorithms that solve both problems restricted to (P5,(s,t)-net)-free graphs in polynomial time. This result generalizes previous works for both problems, and improves existing algorithms when restricted to certain families such as (P5,bull)-free graphs. It turns out that the same approach also serves to solve problems for general graphs in polynomial time whenever γ(G) and γR(G) are fixed (more efficiently than naive algorithms). Moreover, the algorithms described are extremely simple which makes them useful for practical purposes, and as we show in the last section it allows to simplify algorithms for significant classes such as cographs.