Recognizing union-find trees is NP-complete

DOI10.1016/J.IPL.2017.11.003MaRDI QIDQ1685019zbMATH OpenOpenAlexFDO

Authors Kitti Gelle, Szabolcs Iván

Publication date 13 December 2017

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.07462

zbMATH Keywords

complexitydata structuresNP-completenessunion-find treesunion-by-size

Mathematics Subject Classification ID

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

Abstract: Disjoint-Set forests, consisting of Union-Find trees are data structures having a widespread practical application due to their efficiency. Despite them being well-known, no exact structural characterization of these trees is known (such a characterization exists for Union trees which are constructed without using path compression). In this paper we provide such a characterization and show that the decision problem whether a given tree is a Union-Find tree is $NP$-complete.

Recommendations

• Recognizing union-find trees is NP-complete, even without rank info
• Recognizing union-find trees built up using union-by-rank strategy is NP-complete
• The recognition of union trees
• On the Single-Operation Worst-Case Time Complexity of the Disjoint Set Union Problem
• 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 1956218 (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
• 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 built up using union-by-rank strategy 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

(4)

• Recognizing union-find trees is NP-complete, even without rank info
• The recognition of union trees
• Finding compact scheme forests in nested normal form is NP-hard
• 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

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