All Questions

Sometime in the 1980's or 1990's, Bill Thurston proved a theorem regarding the existence of a universal parallel processing machine, using a certain class for such machines having finite deterministic ...

The problem of finding whether a given planar diagram of a graph, with over- and under-crossings, is a linkless embedding or not has unknown complexity (Kawarabayashi et al., 2010). My first question ...

We note that for one dimensional tiling problem of Wang Tile could be represented by a graph. Each cycle on the graph represents a periodic solution. However, is there a well established counter-part ...

Is following decision problem NP-hard / NP-complete: Having vertex-induced subgraph of rectangular lattice graph determine if any Hamiltonian path exists Having vertex-induced subgraph of rectangular ...

In terms of graph isomorphism complexity classes Trees have a polynomial time algorithm and Directed Acyclic Graphs (DAG's) do not (so far). What about Poly-trees (oriented trees)? These are DAG's ...