首页> 外文会议>IAPR International Conference on Discrete Geometry for Computer Imagery >On the Degree Sequence of 3-Uniform Hypergraph: A New Sufficient Condition
【24h】

On the Degree Sequence of 3-Uniform Hypergraph: A New Sufficient Condition

机译:关于3-一致超图的度数序列:一个新的充分条件

获取原文

摘要

The study of the degree sequences of h-uniform hyper-graphs, say h-sequences, was a longstanding open problem in the case of h > 2, until very recently where its decision version was proved to be NP-complete. Formally, the decision version of this problem is: Given π= (d_1,d_2,. . . ,d_n) a non increasing sequence of positive integers, is π the degree sequence of a h-uniform simple hypergraph? Now, assuming P ≠ NP, we know that such an effective characterization cannot exist even for the case of 3-uniform hypergraphs. However, several necessary or sufficient conditions can be found in the literature; here, relying on a result of S. Behrens et al., we present a sufficient condition for the 3-graphicality of a degree sequence and a polynomial time algorithm that realizes one of the associated 3-uniform hypergraphs, if it exists. Both the results are obtained by borrowing some mathematical tools from discrete tomography, a quite recent research area involving discrete mathematics, discrete geometry and combinatorics.
机译:在h> 2的情况下,对h均匀超图的度数序列(例如h序列)的研究是一个长期存在的开放问题,直到最近证明其决策版本是NP完全的。从形式上讲,该问题的判定形式是:给定π=(d_1,d_2,...,d_n)一个非递增的正整数序列,π是h均匀简单超图的度序列吗?现在,假设P≠NP,我们知道即使对于3一致的超图,这种有效的表征也不存在。但是,可以在文献中找到几个必要条件或充分条件。在此,根据S. Behrens等人的结果,我们为度数序列的3图像性和多项式时间算法(如果存在)实现了相关的3均匀超图之一的充分条件。这两个结果都是通过从离散层析成像中借用一些数学工具获得的,离散层析成像是一个涉及离散数学,离散几何和组合数学的最新研究领域。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号