# Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

232 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
84 views

### NP-Hard or PTIME?

I am working on my research problem that essentially boils down to the following question. Consider an $N \times N$ matrix. There is a man at given a starting point $(x,y)$. In each unit of time, the ...
50 views

### Matching of two weighted graphs allowing one-to-many mapping

I am looking for a heuristic for a graph matching problem as follows. Given two graphs: $A$ (consisting of nodes $a_i$) and $B$ (consisting of nodes $b_i$). Typically the size of $B$ is larger than ...
61 views

### About complexity of recovering or learning Bayesian networks

Are there complexity theoretic results about recoverability or learnability of the marginals (of the source vertices) and the conditionals (along each of the edges) of a Bayesian network from having ...
237 views

7k views

### Efficient algorithm to create a directed dependency graph

I am looking for an efficient algorithm to create a graph like this: Initially the graph is filled with x then hs then ...
77 views

### Argument that Graph Isomorphism is polynomial via reduction to CNF

In short we found 3 invertible transformations which imply that Graph Isomorphism is polynomial. Meta reasoning: Isomorphism preserving transformation CNF to "sparse" CNF is possible and ...