tr-announce Mai 2010

tr-announce@lists.rwth-aachen.de

1 Teilnehmer
2 Diskussionen

2010-09: The Structure of the Intersection of Tolerance and Cocomparability Graphs

von Carsten Fuhs

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}.

13 Jahre, 11 Monate

2010-10: Automated Termination Analysis for Logic Programs with Cut

von Carsten Fuhs

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.

13 Jahre, 11 Monate

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

2004

2003

2002

2001

tr-announce Mai 2010