Maximal Linear Arrangement is NP complete on Bipartite Graphs
cs.DM, math.CO
Submitted: 2026-10-08
Updated: 2026-11-06
Terminology
Sources
- Maximum Linear Arrangement: exact algorithms for specific classes of graphs and approximation algorithms for wide classes of graphs
- A Maximum Linear Arrangement Problem on Directed Graphs
Related papers
- Low-Temperature Sampling via Equilibrium Disagreements
- An Improved Bound for Testing k-Colorability
- Temporal Cliques Admit Linear Spanners
- Multiway Partition is FPT for Connectivity Functions
- Profile and neighbourhood complexity of graphs excluding a minor and tree-structured graphs
- Constrained intersection representations and forbidden patterns