Encoding Example

Document last modified:

Given the graph G, provide an encoding for a PATH problem x_i = (G, u, v, k), where G is the graph, u is the source vertex, v is the target vertex, k is an integer specifying the maximum allowable length of a path from u to v.

G = (V, E)
V = {r, s, t, u, v, w, x, y}
E = {(r, s) (r, v) (s, w) (w, t) (w, x) (t, u) (t, x) (u, y) (u, x)}

x₁ = (G, r, y, 5)

e(x₁) = 0101000 0101000 1111011 1110010 0101100 1110011 0101100 1110100 0101100 1110101 0101100 1110110 0101100 1110111 1110111 0101100 1111000 0101100 1111001 1111101 0101100 1111011 0101000 1110010 0101100 1110011 0101001 0101000 1110010 0101100 1110110 0101001 0101000 1110011 0101100 1110111 0101001 0101000 1110111 0101100 1110100 0101001 0101000 1110111 0101100 1111000 0101001 0101000 1110100 0101100 1110101 0101001 0101000 1110100 0101100 1111000 0101001 0101000 1110101 0101100 1111001 0101001 0101000 1110101 0101100 1111000 0101001 1111101 0101001 0101100 1110010 0101100 1111001 0101100 0110101 0101001

Use ASCII for the vertex labels, and the special symbols:

symbol	ASCII	7-bit
r	114	`1110010`
s	115	`1110011`
t	116	`1110100`
u	117	`1110101`
v	118	`1110110`
w	119	`1110111`
x	120	`1111000`
y	121	`1111001`
{	123	`1111011`
}	125	`1111101`
(	40	`0101000`
)	41	`0101001`
,	44	`0101100`
5	53	`0110101`