In machine learning and deep learning, uncertainty quantification helps to accurately assess a model's confidence in its predictions, enabling the rejection of uncertain outcomes in safety-critical applications. However, in scenarios involving AI-assisted decision-making, proposing multiple plausible decisions can be more beneficial than either not making any decisions or risking incorrect ones. Set-valued classification is a relaxation of standard multiclass classification where, in cases of uncertainty, the classifier returns a set of potential labels instead of a single label. Current methods for set-valued classification often suffer from high computational complexity or fail to adequately quantify uncertainty. In this paper, we introduce a novel, computationally efficient approach to set-valued classification leveraging evidential deep learning and subjective logic, explicitly providing a measure of classification uncertainty. Our method employs a dual-head architecture: one head conducts multiclass evidential classification, while the other suggests candidate label sets when uncertainty is high. The proposed approach has linear worstcase computational complexity with respect to the number of classes. Extensive evaluation on several benchmark datasets demonstrates that our method showcases comparable performance to baseline set-valued methods, while being up to 23 times faster at inference on the benchmark datasets.