Timeline for How hard is unshuffling a string?
Current License: CC BY-SA 2.5
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 29, 2010 at 18:37 | comment | added | Per Austrin | For the second question, consider the string 'aaaa'. Purging it removes the edges 1-4 and 2-3, giving a 4-cycle. Two variations of the second greedy step that would also be sufficient and that I could not find any counterexamples to are: 1) A purged graph has a non-nested perfect matching iff it has a perfect matching (this seems incomparable to the greedy step). 2) In a purged graph with a non-nesting perfect matching, every edge is used in some non-nesting perfect matching (this is stronger than both the greedy step and the first item so it should be easier to disprove). | |
| Aug 29, 2010 at 17:07 | comment | added | Jeffε | I'm skeptical about the second greedy phase, but purging the graph seems useful. In the original string context, where the graph is the disjoint union of cliques, can you say anything about the structure of the purged graph? Is it still a disjoint union of cliques? (In other words, can you partition the occurrences of each character in the input string so that characters in different parts cannot be matched?) | |
| Aug 29, 2010 at 15:09 | history | answered | Per Austrin | CC BY-SA 2.5 |