All Questions
8 questions
19
votes
0
answers
782
views
Reference request: Parallel processor theorem of William Thurston
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 ...
- 15.4k
6
votes
2
answers
400
views
Geometric dominating set: NP-complete?
Let $G=(V,E)$ be a geometric graph, a graph embedded in the plane whose edge lengths are
the Euclidean distance between its endpoint vertices.
Say that a set of vertices $D \subseteq V$ is a geometric ...
- 151k
6
votes
2
answers
461
views
Cubic graphs decompositions
There are many interesting computational problems related to connected cubic graph decomposition. For instance, decomposition of cubic graph into a perfect matching and a connected 2-factor (NP-...
- 2,993
3
votes
1
answer
277
views
Theorems about the directed bandwidth of a rooted tree?
Let $T$ be a rooted tree with root $r$. Say an ordering $v_1,\ldots,v_n$ of the vertices of $T$ is a search order if $v_1=r$ and for all $2 \leq i \leq n$, there is $j < i$ such that $v_j$ is the ...
- 4,922
2
votes
0
answers
58
views
Flat or linkless embeddings of graph with fixed projection
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 ...
- 221
2
votes
0
answers
163
views
Graph theoretical representation of Wang Tile
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 ...
- 867
2
votes
0
answers
642
views
Hamiltonian paths in subgraphs of rectangular lattice graphs
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 ...
1
vote
0
answers
172
views
Is there a polynomial time algorithm for Poly-trees (Oriented trees) isomorphism?
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 ...
