We study half-space separation in the convexity of chordless paths of a graph, i.e., monophonic convexity. In this problem, one is given a graph and two (disjoint) subsets of vertices and asks whether these two sets can be separated by complementary convex sets, called half-spaces. While it is known this problem is $\mathbf{NP}$-complete for geodesic convexity -- the convexity of shortest paths -- we show that it can be solved in polynomial time for monophonic convexity.

In [M. M. Kanté, V. Limouzy, A. Mary, and L. Nourine. On the enumeration of minimal dominating sets and related notions. SIAM Journal on Discrete Mathematics, 28(4):1916–1929, 2014.] the authors give an O(n+m) delay algorithm based on neighborhood inclusions for the enumeration of minimal dominating sets in split and P_6-free chordal graphs. In this paper, we investigate generalizations of this technique to P_k-free chordal graphs for larger integers k. In particular, we give O(n+m) and O(n^3 * m) delays algorithms in the classes of P_7-free and P_8-free chordal graphs. As for P_k-free chordal graphs for k >= 9, we give evidence that such a technique is inefficient as a key step of the algorithm, namely the irredundant extension problem, becomes NP-complete.

Automatic synthesis of web services business protocols (BPs) aims at solving algorithmically the problem of deriving a mediator that realizes a BP of a target service using a set of specifications of available services. This problem, and its variants, gave rise to a large number of fundamental research work over the last decade. However, existing works considered this problem under the restriction that the number of instances of an available service that can be involved in a composition is bounded by a constant [Formula: see text] which is fixed a priori. This paper investigates the unbounded variant of this problem using a formal framework in which web service BPs are described by means of finite state machines (FSM). We show that in this context, the protocol synthesis problem can be reduced to that of testing simulation preorder between an FSM and an (infinitely) iterated product of FSMs. Existing results regarding close decision problems in the context of the so-called shuffle languages are rather negative and cannot be directly exploited in our context. In this paper, we develop a novel technique to prove the decidability of testing simulation in our case of interest. We provide complexity bounds for the general protocol synthesis problem and identify two cases of particular interest, namely loop-free target services and hybrid states-free component services, for which protocol synthesis is shown to be respectively NP-COMPETE and EXPTIME-COMPLETE.

We give linear and polynomial time algorithms for computing the hull number of distance-hereditary and chordal graphs, respectively. The complexity of computing the hull number in chordal and distance-hereditary graphs has been open since the introduction of the notion in [M. G. Everett and S. B. Seidman, Discrete Math., 57 (1985), pp. 217--223]. Prior to our result polynomial time algorithms were only known for subclasses of considered graph classes, e.g., split graphs, cographs, interval graphs. Our techniques allow us to give at the same time a linear time algorithm for computing the geodetic number in distance-hereditary graphs. Another consequence of the techniques used is an incremental output-polynomial algorithm to list the set of (inclusion-wise) minimal hull sets in any graphs.

A dominating set $D$ in a graph is a subset of its vertex set such that each vertex is either in $D$ or has a neighbor in $D$. In this paper, we are interested in the enumeration of (inclusionwise) minimal dominating sets in graphs, called the Dom-Enum problem. It is well known that this problem can be polynomially reduced to the Trans-Enum problem in hypergraphs, i.e., the problem of enumerating all minimal transversals in a hypergraph. First, we show that the Trans-Enum problem can be polynomially reduced to the Dom-Enum problem. As a consequence there exists an output-polynomial time algorithm for the Trans-Enum problem if and only if there exists one for the Dom-Enum problem. Second, we study the Dom-Enum problem in some graph classes. We give an output-polynomial time algorithm for the Dom-Enum problem in split graphs and introduce the completion of a graph to obtain an output-polynomial time algorithm for the Dom-Enum problem in $P_6$-free chordal graphs, a proper superclass of split graphs. Finally, we investigate the complexity of the enumeration of (inclusionwise) minimal connected dominating sets and minimal total dominating sets of graphs. We show that there exists an output-polynomial time algorithm for the Dom-Enum problem (or, equivalently, Trans-Enum problem) if and only if there exists one for the following enumeration problems: minimal total dominating sets, minimal total dominating sets in split graphs, minimal connected dominating sets in split graphs, minimal dominating sets in co-bipartite graphs.

The objective of this article is to define an approach towards generating implications with (or without) negation when only a formal context K = (G, M, I) is provided. To that end, we define a two-step procedure which first (i) computes implications

This paper presents an incremental algorithm to compute the covering graph of the lattice generated by a family B of subsets of a totally ordered set X. The implementation of this algorithm has O (((|X| + |B|).|B|).|F|) time complexity, where F is the number of elements in the lattice. This improves the complexity of the previous algorithms which is roughly in O(Min(|X|, |B|)3.|F|). This algorithm may be used in many applications in computer sciences such as the computations of Galois (concept) lattice, the maximal antichains lattice or the Dedekind-MacNeille completion of a partial order. All these lattices can be computed incrementally using this algorithm without increasing time complexity.

Efficient implementation of type inclusion is an important feature of object oriented programming languages with multiple inheritance. The idea is to associate to each type a subset of a set S ={1,..., k } such that type inclusion coincides with subset inclusion. Such an embedding of types into 2 S (the lattice of all subsets of S ) is called a bit‐vector encoding of the type hierarchy. In this paper, we show that most known bit‐vector encoding methods can be inserted on a general theoretical framework using graph coloration, namely the notion of a simple encoding . We use the word simple because all these methods are heuristics for the general bit‐vector encoding problem, known as the 2‐dimension problem. First we provide a correct algorithm for partial orders based on simple encoding, improving the algorithm of Krall, Vitek, and Horspool (1997). Second we show that finding an optimal simple encoding is an NP‐hard problem. We end with a discussion on some practical issues.