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 \emph{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.


翻译:线性之间顺序是线性顺序和间距顺序的交叉点。 对于这一类顺序, 已经知道若干结构性结果。 本文引入了线性中间顺序的一个新的子类。 如果部分顺序是线性顺序和半顺序的交叉点, 我们称之为线性顺序和半顺序的交叉点。 我们为线性 - 中性秩序显示一个特征和多米时间识别算法。 我们还证明, 线性 - 中性秩序是一种可比较性, 表明线性 - 中性秩序的无法比较的图表可以在多边时间得到承认 。

0
下载
关闭预览

相关内容

专知会员服务
138+阅读 · 2021年3月17日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
26+阅读 · 2019年5月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【NIPS2018】接收论文列表
专知
5+阅读 · 2018年9月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
(TensorFlow)实时语义分割比较研究
机器学习研究会
9+阅读 · 2018年3月12日
计算机视觉近一年进展综述
机器学习研究会
8+阅读 · 2017年11月25日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
4+阅读 · 2021年4月13日
Arxiv
7+阅读 · 2018年3月21日
VIP会员
相关VIP内容
专知会员服务
138+阅读 · 2021年3月17日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
26+阅读 · 2019年5月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【NIPS2018】接收论文列表
专知
5+阅读 · 2018年9月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
(TensorFlow)实时语义分割比较研究
机器学习研究会
9+阅读 · 2018年3月12日
计算机视觉近一年进展综述
机器学习研究会
8+阅读 · 2017年11月25日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员