Bodlaender's Theorem states that for every k there is a linear-time algorithm that decides whether an input graph has tree width k and, if so, computes a width-k tree composition. Courcelle's Theorem builds on Bodlaender's Theorem and states that for ...

We consider the coloring problem for mixed graphs, that is, for graphs containing edges and arcs. A mixed coloring c is a coloring such that for every edge [x_i, x_j] c(x_i) ≠ c(x_j) and for every arc (x_p, x_q), c(x_p) < c(x_q). We will analyse the complexity ...

The Probabilistic Satisfiability problem (PSAT) can be considered as a probabilistic counterpart of the classical SAT problem. In a PSAT instance, each clause in a CNF formula is assigned a probability of being true; the problem consists in checking the ...

We describe the first parallel algorithm with optimal speedup for constructing minimum-width tree decompositions of graphs of bounded treewidth. On n-vertex input graphs, the algorithm works in O((log n)²) time using O(n) operations on the EREW PRAM. We ...

In this paper, we give for constant $k$ a linear-time algorithm that, given a graph $G=(V,E)$, determines whether the treewidth of $G$ is at most $k$ and, if so, finds a tree-decomposition of $G$ with treewidth at most $k$. A consequence is that ...

The problem of allocating modules to processors in a distributed system to minimize total costs when the underlying communication graph is a partial k-tree and all costs are linear functions of a real parameter t is considered. It is shown that if the ...