1
vote
0answers
25 views

Directed Hamiltonian Reduction

The reduction function given by Richard Karp in 'Reducibility among combinatorial problems' for Directed Hamiltonian Cycle $\leq_{p}$ Undirected Hamiltonian Cycle goes as follows : for input $G = ...
-2
votes
2answers
98 views

Composition of a system with desired properties

Given the sets $K_1=\{\{a_0,b_1\},\{a_1\},\{b_0\}\}$. $K_2=\{\{c_1,c_0,d_0,e_1\},\{d_1\},\{e_0\}\}$ $K_3=\{\{f_0,f_2,g_0,h_1\},\{f_1,f_3,g_2,h_3\},\{b_1\},\{b_3\},\{c_0\},\{c_2\}\}$ Every item of ...
2
votes
1answer
121 views

Graph enumeration problems which admit recursive solutions

This is an attempt to refine my previous question into something precise enough to admit a resolution. Let $P\;$ be a graph property, let $T_n\left(P\;\right)$ be the set of isomorphism classes of ...
2
votes
1answer
246 views

Restricted read twice BDDs and context free grammars

Several papers give poly-time algorithms for constrained paths on labelled graphs, e.g. [1] Quote: Given an alphabet Σ, a (directed) graph G whose edges are weighted and Σ-labeled, and a formal ...