Improved Bounds for Poset Sorting in the Forbidden-Comparison Regime

DOI10.1007/978-3-319-53007-9_5zbMath1485.68087OpenAlexW2585076947MaRDI QIDQ2971633

Varunkumar Jayapaul, Arindam Biswas, Venkatesh Raman

Publication date: 7 April 2017

Published in: Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-53007-9_5

zbMATH Keywords

complexityposetsortingcomparability graphchordal graphquery

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Partial orders, general (06A06) Searching and sorting (68P10) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Finding kings in tournaments

Cites Work

• Sorting and Selection in Posets
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Matching Nuts and Bolts in O(n log n) Time
• Sorting under Forbidden Comparisons