• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>SOFSEM 2009: Theory and practice of computer science >The Simple Reachability Problem in Switch Graphs
【24h】

The Simple Reachability Problem in Switch Graphs

机译：切换图中的简单可达性问题

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

摘要

Switch graphs as introduced in [Coo03] are a natural generalization of graphs where edges are interpreted as train tracks connecting switches: Each switch has an obligatory incident edge which has to be used by every path going through this switch. We prove that the simple reachability problem in switch graphs is NP-complete in general, but we describe a polynomial time algorithm for the undirected case. As an application, this can be used to find an augmenting path for bigamist matchings and thus iteratively construct a maximum bigamist matching for a given bipartite graph with red and blue edges, that is the maximum set of vertex disjoint triples consisting of one bigamist vertex connected to two monogamist vertices with two different colors. This this gives an independent direct solution to an open problem in [SGYB05].
机译：[Coo03]中引入的开关图是图的自然概括，其中边被解释为连接开关的火车轨道：每个开关都有一个强制性入射边，通过该开关的每条路径都必须使用该入射边。我们证明了切换图中的简单可达性问题通常是NP完全的，但是我们针对无向情况描述了多项式时间算法。作为一个应用程序，它可以用于找到重婚配比的增广路径，从而针对具有红色和蓝色边缘的给定二分图迭代地构造最大重婚配比，即最大的顶点不相交三元组（由一个相连的重婚顶点组成）到具有两种不同颜色的两个一夫一妻制顶点。这为[SGYB05]中的未解决问题提供了独立的直接解决方案。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号