Solution of the Linear Ordering Problem (NP=P)

2003/03/14 by Givi Bolotashvili, G. G. Bolotashvili, Bolotashvili, Givi
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #F.2.0 #FOS: Computer and information sciences #VLSI and FPGA Design Techniques #cs.CC #cs.DM

paper · pdf · doi:10.48550/arxiv.cs/0303008

arxiv created 2003/03/14 · openalex publication_date 2003/03/14 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A polynomial algorithm is obtained for the NP-complete linear ordering problem.

Related

• Transitions from P to NP-hardness: the case of the Linear Ordering Problem
• Rankability and Linear Ordering Problem: New Probabilistic Insight and Algorithms
• A Multi-parent Memetic Algorithm for the Linear Ordering Problem
• On algorithms to find p-ordering
• A Memetic Algorithm for the Linear Ordering Problem with Cumulative Costs