2019/07/18 by Asahi Takaoka, Takaoka, Asahi
Computer Science · Mathematics · #05C62 #05C75 #06A07 #68R10 #Advanced Graph Theory Research #Combinatorics (math.CO) #Constraint Satisfaction and Optimization #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO #msc:05C62 #msc:05C75 #msc:06A07 #msc:68R10 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1907.07845
28 pages
openalex publication_date 2019/07/18 · arxiv created 2021/05/10 · arxiv updated 2021/05/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A linear-interval order is the intersection of a linear order and an interval order. For this class of orders, several structural results have been known. This paper introduces a new subclass of linear-interval orders. We call a partial order a linear-semiorder if it is the intersection of a linear order and a semiorder. We show a characterization and a polynomial-time recognition algorithm for linear-semiorders. We also prove that being a linear-semiorder is a comparability invariant, showing that incomparability graphs of linear-semiorders can be recognized in polynomial time.