Timeline for polytime transformation from a graph to a set of binary strings
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 18, 2015 at 14:26 | comment | added | Tom van der Zanden | You are right about the $2k$ v.s. $k$ thing. With regards to modifying the graph in the general case, you don't need to actually modify the graph, you just need to define $f$ as if these additional vertices existed, but can forget that these vertices exist afterwards. All you are doing is padding the resulting string with extra $0$'s and $1$'s so that $f(v)$ always has the same number of $1$'s (namely, equal to the maximum degree of the graph). | |
| Jan 18, 2015 at 14:22 | history | edited | Tom van der Zanden | CC BY-SA 3.0 |
added 2 characters in body
|
| Jan 18, 2015 at 13:54 | vote | accept | user109711 | ||
| Jan 18, 2015 at 13:36 | comment | added | user109711 | In your proposal, don't we rather get $d_H(f(v), f(u)) = 2k-2$ if $u$ and $v$ are adjacent, $2k$ otherwise? May you please confirm it? Well, this would work still work but I need to make sure of that. About your last sentence on the general case, then a modification of the graph seems necessary (adding a vertex), which I cannot allow. Overall, it is fine for the problem I am interested in to restrict the input graph to a cubic one, so everything would be fine for me. | |
| Jan 18, 2015 at 11:24 | history | answered | Tom van der Zanden | CC BY-SA 3.0 |