Recognizing union-find trees is NP-complete, even without rank info

DOI10.1142/S0129054119400276MaRDI QIDQ5205041zbMATH OpenOpenAlexWikidataFDO

Authors 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

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

Recommendations

• Recognizing union-find trees built up using union-by-rank strategy is NP-complete
• Recognizing union-find trees is NP-complete
• The recognition of union trees
• Probabilistic Analysis of Disjoint Set Union Algorithms
• Efficient Union-Find for planar graphs and other sparse graph classes

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1874382 (Why is no real title available?)
• An improved equivalence algorithm
• Border array on bounded alphabet
• Certifying algorithms
• Counting Parameterized Border Arrays for a Binary Alphabet
• Cover array string reconstruction
• Efficiency of a Good But Not Linear Set Union Algorithm
• Efficient validation and construction of border arrays and validation of string matching automata
• Experimental algorithmics. From algorithm design to robust and efficient software
• Inferring strings from suffix trees and links on a binary alphabet
• Introduction to algorithms
• Mathematical Foundations of Computer Science 2003
• On the combinatorics of suffix arrays
• Recognizing union-find trees is NP-complete
• Reverse engineering prefix tables
• The recognition of union trees
• Unification: a multidisciplinary survey
• Validating the Knuth-Morris-Pratt failure function, fast and online
• Verifying and enumerating parameterized border arrays
• Words over an ordered alphabet and suffix permutations

Cited in

(5)

• The recognition of union trees
• Recognizing union-find trees is NP-complete
• On suffix tree detection
• On suffix tree detection
• Recognizing union-find trees built up using union-by-rank strategy is NP-complete

This page was built for publication: Recognizing union-find trees is NP-complete, even without rank info

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5205041)