Giménez, Omer, Godoy, Guillem, Maneth, Sebastian
Finite-state tree automata are a well studied formalism for representing term languages. This paper studies the problem of determining the regularity of the set of instances of a finite set of terms...
Causal Graphs and Structurally Restricted Planning (2009)
The causal graph is a directed graph that describes the variable dependencies present in a planning instance. A number of papers have studied the causal graph in both practical and theoretical...
Act Local, Think Global: Width Notions for Tractable Planning (2009)
Many of the benchmark domains in AI planning are tractable on an individual basis. In this paper, we seek a theoretical, domain-independent explanation for their tractability. We present a family of...
On the number of K3,3-minor-free and maximal K3,3-minor-free graphs (2006)
Gerke, Stefanie, Giménez, Omer, Noy, Marc, Weissl, Andreass
"Vegeu el resum a l'inici del document del fitxer adjunt."
Solving planning domains with polytree causal graphs is NP-complete (2006)
We show that solving planning domains on binary variables with polytree causal graph is \NP-complete. This is in contrast to a polynomial-time algorithm of Domshlak and Brafman that solves these...
On the number of series parallel and outerplanar graphs (2005)
Manuel Bodirsky, Omer Giménez, Mihyun Kang, Marc Noy
We show that the number gn of labelled series-parallel graphs on n vertices is asymptotically gn ∼ g · n −5/2 γ n n!, where γ and g are explicit computable constants. We show that the number...
On the number of series parallel and outerplanar graphs (2005)
Manuel Bodirsky, Omer Giménez, Mihyun Kang, Marc Noy
Abstract. We show that the number gn of labelled series-parallel graphs on n vertices is asymptotically gn ∼ g · n −5/2 γ n n!, where γ and g are explicit computable constants. We show that...
Computing the Tutte polynomial on graphs of bounded clique-width (2005)
Abstract. The Tutte polynomial is a notoriously hard graph invariant, and efficient algorithms for it are known only for a few special graph classes, like for those of bounded tree-width. The notion...
Computing the Tutte polynomial on graphs of bounded clique-width (2005)
Abstract. The Tutte polynomial is a notoriously hard graph invariant, and efficient algorithms for it are known only for a few special graph classes, like for those of bounded tree-width. The notion...