Recognizing Union-Find Trees is NP-Complete, Even Without Rank Info

DOI10.1142/S0129054119400276zbMath1427.68059OpenAlexW2974852703WikidataQ127227329 ScholiaQ127227329MaRDI QIDQ5205041

Kitti Gelle, Szabolcs Iván

Publication date: 10 December 2019

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054119400276

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Certifying algorithms
• Inferring strings from suffix trees and links on a binary alphabet
• Verifying and enumerating parameterized border arrays
• Validating the Knuth-Morris-Pratt failure function, fast and online
• Recognizing union-find trees is NP-complete
• Experimental algorithmics. From algorithm design to robust and efficient software
• A suffix tree or not a suffix tree?
• The recognition of union trees
• On the combinatorics of suffix arrays
• Cover Array String Reconstruction
• Counting Parameterized Border Arrays for a Binary Alphabet
• Efficient validation and construction of border arrays and validation of string matching automata
• Unification: a multidisciplinary survey
• Efficiency of a Good But Not Linear Set Union Algorithm
• Words over an ordered alphabet and suffix permutations
• An improved equivalence algorithm
• REVERSE ENGINEERING PREFIX TABLES
• Mathematical Foundations of Computer Science 2003

This page was built for publication: Recognizing Union-Find Trees is NP-Complete, Even Without Rank Info