On the complexity of partial order properties

DOI10.1023/A:1006422023869zbMATH Open0963.06002MaRDI QIDQ1590180FDOQ1590180

Authors: Stefan Felsner, Ravi Kant, C. Pandu Rangan, Dorothea Wagner 

Publication date: 28 June 2001

Published in: Order (Search for Journal in Brave)

Recommendations

• scientific article; zbMATH DE number 512933
• A lower bound for the complexity of information networks for one partial order relation
• On the complexity of interval orders and semiorders
• On the computational complexity of ordered subgraph recognition
• Sorting and Recognition Problems for Ordered Sets

zbMATH Keywords

adversaryevasivenessrecognition complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Combinatorics of partially ordered sets (06A07)

Cited In (16)

• The Complexity of Order Type Isomorphism
• Sorting and Recognition Problems for Ordered Sets
• A characteristic condition for simple partial ordering relations
• On optimal approximations of arbitrary relations by partial orders
• The solution space of sorting with recurring comparison faults
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The complexity of the partial order dimension problem: closing the gap
• Title not available (Why is that?)
• On the complexity of interval orders and semiorders
• The solution space of sorting with recurring comparison faults
• Title not available (Why is that?)
• On partial order characterizations of information structures
• Computing and Verifying Depth Orders
• The fine-grained complexity of multi-dimensional ordering properties

This page was built for publication: On the complexity of partial order properties

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