Recognizing union-find trees is NP-complete

DOI10.1016/J.IPL.2017.11.003zbMATH Open1423.68191arXiv1510.07462OpenAlexW2963334127MaRDI QIDQ1685019FDOQ1685019

Szabolcs Iván, Kitti Gelle

Publication date: 13 December 2017

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

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.

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

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

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)

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
• Validating the Knuth-Morris-Pratt failure function, fast and online
• A suffix tree or not a suffix tree?
• The recognition of union trees
• Recognizing union-find trees built up using union-by-rank strategy is NP-complete
• Title not available (Why is that?)

Cited In (3)

• Finding compact scheme forests in nested normal form is NP-hard
• Recognizing Union-Find Trees is NP-Complete, Even Without Rank Info
• The recognition of union trees

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)