应用数学学报
首页  |  期刊介绍  |  编 委 会  |  投稿指南  |  期刊订阅  |  广告服务  |  相关链接  |  下载中心  |  联系我们  |  留言板
 
应用数学学报 英文版  
   
   
高级检索 »  
应用数学学报  1995, Vol. 18 Issue (2): 176-178    DOI:
论文 最新目录 | 下期目录 | 过刊浏览 | 高级检索  |   
关于3-正则子图问题的一个注记
于濂, 刘彦佩
中国科学院应用数学研究所, 北京100080
A NOTE ON THE 3_REGULAR SUBGRAPH PROBLEM
YU LIAN, LIU YANPEI
Institute of Applied Mathematics, the Chinese Academy of Sciences, Beijing 100080
 全文: PDF (2218 KB)   HTML ( KB)   输出: BibTeX | EndNote (RIS)      背景资料
摘要 这篇注记证明判断一个图是否有3-正则子图的问题,即使对于节点次不超过4的平面图,仍然是NP-完全的。而且,此结果是最好的可能。
服务
把本文推荐给朋友
加入我的书架
加入引用管理器
E-mail Alert
RSS
作者相关文章
于濂
刘彦佩
关键词平面图   正则子图问题   满足性问题   NP-完全性     
Abstract: This note shows that the problem of justifying if a graph has a 3-regular subgraph is still NP-complete even for a planar graph with valency not greater than four. The result is of course in the best possible case for the valent restriction.
Key wordsPlanar graph   Regular subgraph problem   satisfiability problem NP-completeness   
收稿日期: 1992-11-03;
引用本文:   
于濂,刘彦佩. 关于3-正则子图问题的一个注记[J]. 应用数学学报, 1995, 18(2): 176-178.
YU LIAN,LIU YANPEI. A NOTE ON THE 3_REGULAR SUBGRAPH PROBLEM[J]. Acta Mathematicae Applicatae Sinica, 1995, 18(2): 176-178.
 
[1] M.R. Garey and D.S. Johnson, Computers and Intractability:A Guide to the Theory of NP-compliteness,W.H. Freeman, San Francisco, 1979.
[2] Iain A. Stewart, Deciding whether a Planar Graph has a Cubic Subgraph is NP-complete, Discrete Math., 1994, 126:347-357.
没有找到本文相关文献
  版权所有 © 2009 应用数学学报编辑部   E-mail: amas@amt.ac.cn
京ICP备05002806号-9