Dorit Dor

We consider a natural family of motion planning problems with movable obstacles and obtain hardness results for them. Some members of the family are shown to be PSPACE-complete thus improving and extending (and also simplifying) a previous NP-hardness result of Wilfong. The family considered includes a motion planning problem which forms the basis of a popular computer game called SOKOBAN. The decision problem corresponding to SOKOBAN is shown to be NP-hard. The motion planning problems… רוצה לראות יותר

We consider a natural family of motion planning problems with movable obstacles and obtain hardness results for them. Some members of the family are shown to be PSPACE-complete thus improving and extending (and also simplifying) a previous NP-hardness result of Wilfong. The family considered includes a motion planning problem which forms the basis of a popular computer game called SOKOBAN. The decision problem corresponding to SOKOBAN is shown to be NP-hard. The motion planning problems considered are related to the “warehouseman's problem” considered by Hopcroft, Schwartz and Sharir, and to geometric versions of the motion planning problem on graphs considered by Papadimitriou, Raghavan, Sudan and Tamaki. רוצה לראות פחות

An H-decomposition of a graph G=(V,E) is a partition of E into subgraphs isomorphic to H. Given a fixed graph H, the H-decomposition problem is to determine whether an input graph G admits an H-decomposition.

In 1980, Holyer conjectured that H-decomposition is NP-complete whenever H is connected and has three edges or more. Some partial results have been obtained since then. A complete proof of Holyer's conjecture is the content of this paper. The characterization problem of all graphs H… רוצה לראות יותר

An H-decomposition of a graph G=(V,E) is a partition of E into subgraphs isomorphic to H. Given a fixed graph H, the H-decomposition problem is to determine whether an input graph G admits an H-decomposition.

In 1980, Holyer conjectured that H-decomposition is NP-complete whenever H is connected and has three edges or more. Some partial results have been obtained since then. A complete proof of Holyer's conjecture is the content of this paper. The characterization problem of all graphs H for which H-decomposition is NP-complete is hence reduced to graphs where every connected component contains at most two edges. רוצה לראות פחות

We describe an algorithm for selecting the αn-th largest element (where 0<α<1), from a totally ordered set of n elements, using at most (1+(1+o(1))H(α))·n comparisons where H(α) is the binary entropy function and the o(1) stands for a function that tends to 0 as α tends to 0. For small values of α this is almost the best possible as there is a lower bound of about (1+H(α))·n comparisons. The algorithm obtained beats the global 3n upper bound of Schönhage, Paterson and Pippenger for… רוצה לראות יותר

We describe an algorithm for selecting the αn-th largest element (where 0<α<1), from a totally ordered set of n elements, using at most (1+(1+o(1))H(α))·n comparisons where H(α) is the binary entropy function and the o(1) stands for a function that tends to 0 as α tends to 0. For small values of α this is almost the best possible as there is a lower bound of about (1+H(α))·n comparisons. The algorithm obtained beats the global 3n upper bound of Schönhage, Paterson and Pippenger for α<1/3. רוצה לראות פחות

A Partially directed acyclic graph, (pdag), is a graph which contains both directed
and undirected edges, with no directed cycle in its directed subgraph. An oriented
extension of a pdag G is a fully directed acyclic graph (dag) on the same underlying
set of edges, with the same orientation on the directed subgraph of G and the same set of
vee-structures. A vee-structure is formed by two edges, directed toward a common head,
while their tails are nonadjacent. A simple… רוצה לראות יותר

A Partially directed acyclic graph, (pdag), is a graph which contains both directed
and undirected edges, with no directed cycle in its directed subgraph. An oriented
extension of a pdag G is a fully directed acyclic graph (dag) on the same underlying
set of edges, with the same orientation on the directed subgraph of G and the same set of
vee-structures. A vee-structure is formed by two edges, directed toward a common head,
while their tails are nonadjacent. A simple polynomial-time algorithm is presented,
to solve the following problem: Given a pdag, does it admit an oriented extension?
The problem was stated by Verma and Pearl, while studying the existence of causal
explanation to a given set of observed independencies. רוצה לראות פחות