...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>SIAM Journal on Discrete Mathematics >RETRACTIONS TO PSEUDOFORESTS
【24h】

RETRACTIONS TO PSEUDOFORESTS

机译：伪造林的撤回

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

For a fixed graph H, let Ret(H) denote the problem of deciding whether a given input graph is retractable to H. We classify the complexity of Ret(H) when H is a graph (with loops allowed) where each connected component has at most one cycle, i.e., a pseudoforest. In particular, this result extends the known complexity classifications of Ret(H) for reflexive and irreflexive cycles to general cycles. Our approach is based mainly on algebraic techniques from universal algebra that previously have been used for analyzing the complexity of constraint satisfaction problems.
机译：对于固定图H，让Ret（H）表示确定给定输入图是否可伸缩到H的问题。当H是一个图（允许循环）时，每个连接的组件都有最多一个周期，即一个伪林。特别地，该结果将自反循环和非自反循环的Ret（H）的已知复杂度分类扩展到普通循环。我们的方法主要基于通用代数的代数技术，该技术以前已用于分析约束满足问题的复杂性。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号