31 citations · 104 across the 14 of their papers we have counts for
14 papers
Planning over Chain Causal Graphs for Variables with Domains of Size 5 Is NP-Hard
Omer Giménez, Anders Jonsson
Recently, considerable focus has been given to the problem of determining the boundary between tractable and intractable planning problems. In this paper, we study the complexity o…
Maximum degree in minor-closed classes of graphs
Omer Gimenez, Dieter Mitsche, Marc Noy
Given a class of graphs G closed under taking minors, we study the maximum degree Δ_n of random graphs from G with n vertices. We prove several lower and upper bounds that hold wit…
The Complexity of Planning Problems With Simple Causal Graphs
Omer Giménez, Anders Jonsson
We present three new complexity results for classes of planning problems with simple causal graphs. First, we describe a polynomial-time algorithm that uses macros to generate plan…
The maximum degree of planar graphs I. Series-parallel graphs
Michael Drmota, Omer Gimenez, Marc Noy
We prove that the maximum degree of a random series-parallel graph with vertices satisfies in probability, and for a c…
Asymptotic enumeration and limit laws for graphs of fixed genus
Guillaume Chapuy, Eric Fusy, Omer Gimenez +2
It is shown that the number of labelled graphs with n vertices that can be embedded in the orientable surface S_g of genus g grows asymptotically like …
Degree distribution in random planar graphs
Michael Drmota, Omer Gimenez, Marc Noy
We prove that for each , the probability that a root vertex in a random planar graph has degree tends to a computable constant , so that the expected number of vert…