A weighted version of the jump number problem on two-dimensional orders is NP-complete

DOI10.1023/A:1024417802690zbMath1027.06002OpenAlexW97390432MaRDI QIDQ1404375

Stéphan Ceroi

Publication date: 21 August 2003

Published in: Order (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1023/a:1024417802690

zbMATH Keywords

dimensionNP-completenessjump numbermaximal independent settwo-dimensional orders

Mathematics Subject Classification ID

Partial orders, general (06A06) Number-theoretic algorithms; complexity (11Y16) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Jump Number of Two-Directional Orthogonal Ray Graphs

This page was built for publication: A weighted version of the jump number problem on two-dimensional orders is NP-complete