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

DOI10.1142/S0129054119400276zbMATH Open1427.68059OpenAlexW2974852703WikidataQ127227329 ScholiaQ127227329MaRDI QIDQ5205041FDOQ5205041

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (5)

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

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)