Parallel power system restoration (PPSR) restores isolated sections (islands) of the network in parallel, thus the overall restoration process is accelerated. These islands are defined during the preparation stage of PPSR as part of a sectionalising strategy (SS). During this process, it is important that the operators only use updated post-blackout system information. This study proposes a new methodology based on the 'cut-set' matrix defined in graph theory, which can identify a shortlist of suitable SSs that satisfy the critical PPSR constraints in a few minutes. This short list of SSs, not identified in previous works, can be presented to the operators to help them select a restoration plan that is tailored to the specific changes in topology and asset availability that the blackout has caused. The methodology is illustrated using the IEEE 9-bus system, and validated using the IEEE 118-bus and the Polish 3375-bus system to demonstrate the efficiency of the new approach for large-scale networks. Multiple case studies are developed to demonstrate the adaptability of the methodology to different system conditions, for example, the unavailability of assets. In every case, the methodology quickly identified a number of SSs that create suitable islands for parallel restoration.