On the Hardness of Optimal Vertex Relabeling and Restricted Vertex Relabeling

DOI10.1007/978-3-319-19929-0_1zbMath1432.68331OpenAlexW839871685MaRDI QIDQ2942241

Amihood Amir, Benny Porat

Publication date: 20 August 2015

Published in: Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-19929-0_1

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Token Swapping on Trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient special cases of pattern matching with swaps
• Parameterized matching on non-linear structures
• Bounds for sorting by prefix reversal
• Overlap matching.
• Improved approximate pattern matching on hypertext
• Approximate swapped matching.
• Swap and mismatch edit distance
• Approximate String Matching with Address Bit Errors
• k-Mismatch with Don’t Cares
• Pattern matching with address errors
• On the Diameter of the Pancake Network
• Pattern Matching with Swaps
• Pattern Matching in Hypertext
• Approximate String Matching with Swap and Mismatch
• Function Matching
• On the Cost of Interchange Rearrangement in Strings

This page was built for publication: On the Hardness of Optimal Vertex Relabeling and Restricted Vertex Relabeling