A Paper on CSTNs @┬áTIME2015 (Sept 23-25, 2015, University of Kassel, Germany).

Our Paper “Dynamic Consistency of Conditional Simple Temporal Networks via Mean Payoff Games: a Singly-Exponential Time DC-Checking” was accepted to the “22nd International Symposium on Temporal Representation and Reasoning (TIME2015)“.

TIME2015 will be held at University of Kassel, Germany (September 23-25, 2015).

This is a joint work with R. Rizzi.
Pre-print link: manuscript, presentation.



An Improved Upper Bound on Maximal Clique Listing via Rectangular Fast Matrix Multiplication

The first output-sensitive algorithm for the Maximal Clique Listing problem was given by Tsukiyama et. al. in 1977. As any algorithm falling within the Reverse Search paradigm, it performs a DFS visit of a directed tree (the RS-tree) having the objects to be listed (i.e. maximal cliques) as its nodes. In a recursive implementation, the RS-tree corresponds to the recursion tree of the algorithm. The time delay is given by the cost of generating the next child of a node, and Tsukiyama showed it is O(mn). In 2004, Makino and Uno sharpened the time delay to O(n^{\omega}) by generating all the children of a node in one single shot performed by computing a square fast matrix multiplication. In this paper, we further improve the asymptotics for the exploration of the same RS-tree by grouping the offsprings’ computation even further. Our idea is to rely on rectangular fast matrix multiplication in order to compute all children of n^2 nodes in one shot. According to the current upper bounds on square and rectangular fast matrix multiplication, with this the time delay improves from O(n^{2.3728639}) to O(n^{2.093362}).

Download: Manuscript.