Global preferential consistency for the topological sorting-based maximal spanning tree problem
This work addresses a domain-specific problem in computational optimization for spanning trees, presenting an incremental advancement.
The paper tackles the problem of finding maximal spanning trees with preferential consistency by introducing a new compact representation of preferences and comparing it with Pareto-based multiobjective approaches, resulting in an efficient algorithm for solving the preferential consistency problem.
We introduce a new type of fully computable problems, for DSS dedicated to maximal spanning tree problems, based on deduction and choice: preferential consistency problems. To show its interest, we describe a new compact representation of preferences specific to spanning trees, identifying an efficient maximal spanning tree sub-problem. Next, we compare this problem with the Pareto-based multiobjective one. And at last, we propose an efficient algorithm solving the associated preferential consistency problem.