.png){kind=icon}
Return
Indexed Subset Construction: A Structured Algorithmic Framework
.png){kind=icon}
PRE
AI
DOI：10.3390/a19050397.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This paper studies subset construction in NP-complete problems from the perspective of structured exploration of combinatorial search spaces. Classical approaches rely on exhaustive enumeration of subsets, which leads to exponential growth in time and memory requirements. To address this limitation, we introduce an indexed framework based on the correspondence between a finite set and its associated index set. Within this framework, subsets are represented as ordered index sequences, allowing subset construction to be reformulated as a constraint-guided search process over index space. Candidate subsets are characterized by numerical descriptors derived from their indices (referred to as index certificates), which guide and filter the construction process. Subset generation is further organized through admissible index intervals that restrict feasible transitions and reduce the effective search space. The framework is based on an index-based representation and structured traversal of pairwise index combinations. Computational experiments on representative instances illustrate the behavior of the indexed construction procedure and indicate its efficiency relative to classical enumeration-based methods for small and medium-sized instances. The proposed approach provides a structured perspective on combinatorial search and offers a basis for further development of algorithms based on constrained exploration of subset structures.
Keywords:
combinatorial search
subset construction
indexed representation
constraint-guided search
subset sum problem
NP-complete problems