All Questions
8 questions with no upvoted or accepted answers
8
votes
0
answers
152
views
Disjoint Rooted Paths with Specified Patterns
Let $S:=$ { $s_i : i \in [k]$ } and $T:=$ { $t_i : i \in [k]$ } be disjoint subsets of vertices of a graph $G$. Furthermore, let $A$ be a subset of $S_k$ (the symmetric group on $[k]$). A set of ...
- 32.1k
2
votes
0
answers
54
views
Do there (or might there) exist computable invariants for Aut(G)-invariant subgraphs of a graph G?
I am interested in algorithms for computing all subgraphs (not necessarily induced) of a graph $G$ up to $Aut(G)$ isomorphism. I had the idea of partitioning the edges of the graph like so
$$\{F|E(G)\...
- 161
2
votes
0
answers
106
views
Decomposing a planar graph
Thomassen proved that the vertex set of every planar graph can be decomposed into two sets inducing a 1-degenerate graph and a 2-degenerate graph, respectively (C. Thomassen, Decomposing a planar ...
- 3,153
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
52
views
Standard test for the recognition of toroidal graphs
Is there a standard test for the recognition of toroidal graphs? I have been using the Boyer–Myrvold planarity algorithm, which has a MATLAB and C++ implementation.
- 11
1
vote
1
answer
298
views
maximal sets of vertices that avoids a clique
I am looking for some known algorithm that finds, for a given graph, all the maximal sets of vertices that avoid a clique of some given size $k$. I'd prefer one written in MATLAB, but other languages ...
- 11
0
votes
0
answers
78
views
Sum of products on a directed acyclic graph
Is there a textbook/paper that I can reference for the following problem? I am looking for a concise proof that I can cite.
Let $G=(V,E)$ be a weighted directed acyclic graph, and consider
$s,t\in V$....
- 101
0
votes
0
answers
97
views
Shortest hyperpath algorithm in intuitionistic fuzzy hypergraphs
I was looking for an algorithm to calculate the shortest hyperpath in intuitionistic fuzzy hypergraphs and I found only this article (which propose two algorithms).
Are there any others algorithms ...
- 101