tr-announce

Download

tr-announce@lists.rwth-aachen.de

May 2010

1 participants
2 discussions

2010-09: The Structure of the Intersection of Tolerance and Cocomparability Graphs
by Carsten Fuhs 21 May '10

21 May '10

The following technical report is available from http://aib.informatik.rwth-aachen.de: The Structure of the Intersection of Tolerance and Cocomparability Graphs George B. Mertzios, Shmuel Zaks AIB 2010-09 Tolerance graphs have been extensively studied since their introduction in 1982 \cite{GoMo82}, due to their interesting structure and their numerous applications, as they generalize both interval and permutation graphs in a natural way. It has been conjectured in 1984 that the intersection of tolerance and cocomparability graphs coincides with bounded tolerance graphs \cite{GolumbicMonma84}. The conjecture has been proved for complements of trees, and later extended to complements of bipartite graphs, and these are the only known results so far. Furthermore, it is known that the intersection of tolerance and cocomparability graphs is contained in the class of trapezoid graphs. In this article we almost prove the conjecture given in \cite{GolumbicMonma84}. Namely, we prove that the conjecture is true for every graph $G$, whose tolerance representation $R$ satisfies a slight assumption. This assumption is satisfied by a wide variety of graph classes; for example, our results immediately imply the above mentioned correctness of the conjecture for complements of bipartite graphs. In particular, our assumption still holds if $R$ has exactly one unbounded vertex, or even if for every unbounded vertex $u$ in $R$ there is no other unbounded vertex $v$, such that the neighborhood of $v$ is strictly included in the neighborhood of $u$. Our results are based on the intersection model of parallelepipeds in the 3-dimensional space for tolerance graphs, which has been recently introduced in \cite{MSZ-Model-SIDMA-09}. The present article illustrates how this intersection model can be used to derive also structural results, besides its usefulness in the design of efficient algorithms \cite{MSZ-Model-SIDMA-09}. The proofs of our results rely on the fact that $G$ has simultaneously such a representation, as well as a trapezoid representation. The techniques presented in this article are new, provide geometrical insight for the structure of the graphs that are both tolerance and cocomparability, and it can be expected that they are extendable to the most general case, answering in the affirmative the conjecture of \cite{GolumbicMonma84}.

1 0

2010-10: Automated Termination Analysis for Logic Programs with Cut
by Carsten Fuhs 14 May '10

14 May '10

The following technical report is available from http://aib.informatik.rwth-aachen.de: Automated Termination Analysis for Logic Programs with Cut Peter Schneider-Kamp, Jürgen Giesl, Thomas Ströder, Alexander Serebrenik, René Thiemann AIB 2010-10 Termination is an important and well-studied property for logic programs. However, almost all approaches for automated termination analysis focus on definite logic programs, whereas real-world Prolog programs typically use the cut operator. We introduce a novel pre-processing method which automatically transforms Prolog programs into logic programs without cuts, where termination of the cut-free program implies termination of the original program. Hence after this pre-processing, any technique for proving termination of definite logic programs can be applied. We implemented this pre-processing in our termination prover AProVE and evaluated it successfully with extensive experiments.

1 0