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

DOI10.1023/A:1024417802690MaRDI QIDQ1404375zbMATH OpenOpenAlexFDO

Authors 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

dimensionjump numbermaximal independent setNP-completenesstwo-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)

Recommendations

• NP-completeness properties about linear extensions
• Tackling the jump number of interval orders
• Weighted domination on cocomparability graphs
• A refined analysis on the jump number problem of interval orders
• Jump number of dags having Dilworth number 2

Cited in

(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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1404375)