首页> 外文会议>Fundamentals of computation theory >Reachability in K_(3,3)-Free Graphs and K_5-Free Graphs Is in Unambiguous Log-Space

【24h】

Reachability in K_(3,3)-Free Graphs and K_5-Free Graphs Is in Unambiguous Log-Space

机译：无K_（3,3）图和K_5无图的可达性在明确的日志空间中

获取原文

获取原文并翻译 | 示例

页面导航

摘要
著录项
相似文献
相关主题

摘要

We show that the reachability problem for directed graphs that are either K_(3,3)-free or K_5-free is in unambiguous log-space, UL ∩ coUL. This significantly extends the result of Bourke, Tewari, and Vin-odchandran that the reachability problem for directed planar graphs is in UL∩ coUL.

机译：我们表明，无K_（3,3）或无K_5的有向图的可达性问题在明确的日志空间UL∩coUL中。这大大扩展了Bourke，Tewari和Vin-odchandran的结果，即有向平面图的可及性问题在于UL∩coUL。

著录项

来源
《Fundamentals of computation theory》|2009年|323-334|共12页
会议地点 Wroclaw(PL);Wroclaw(PL)
作者
Thomas Thierauf; Fabian Wagner;
展开▼
作者单位

Fak. Elektronik und Informatik, HTW Aalen, 73430 Aalen, Germany;

Inst. fuer Theoretische Informatik, Universitaet Ulm, 89069 Ulm, Germany;

展开▼
会议组织
原文格式 PDF
正文语种 eng
中图分类理论、方法;
关键词

相似文献

外文文献
中文文献
专利

1. Reachability in K_{3,3}-free Graphs and K_5-free Graphs is in Unambiguous Log-Space [J] . Fabian Wagner, Thomas Thierauf Electronic Colloquium on Computational Complexity . 2009,第131期

机译：不含K_ {3,3}的图和不含K_5的图的可达性在明确的日志空间中
2. Reachability in K_{3,3}-free and K_5-free Graphs is in Unambiguous Logspace [J] . Thomas Thierauf, Fabian Wagner Chicago Journal of Theoretical Computer Science . 2014,第2期

机译：无K_ {3,3}和无K_5图中的可达性在明确的日志空间中
3. Graph Isomorphism for K_{3,3}-free and K_5-free graphs is in Log-space [J] . Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, LIPIcs : Leibniz International Proceedings in Informatics . 2009,第2期

机译：无K_ {3,3}和无K_5图的图同构在对数空间中
4. Reachability in K_(3,3)-Free Graphs and K_5-Free Graphs Is in Unambiguous Log-Space [C] . Thomas Thierauf, Fabian Wagner International Symposium Fundamentals of Computation Theory . 2009

机译：在K_（3,3）中的可达性 - 免费图形和k_5-free图形是明确的日志空间
5. Kinetic, kinematic and electromyographic study of the effects of reach velocity and postural set on postural adjustments associated with reaching in seated subjects. [D] . Moore, Sandra. 1990

机译：动力学，运动学和肌电图研究，就坐位受试者的伸直速度和姿势设定对与伸直相关的姿势调整的影响。
6. Unambiguous Concept Mapping in Radiology Reports:Graphs of Consistent Concepts [O] . Pawel Matykiewicz, John Pestian, Wlodzislaw Duch, 2006

机译：放射学报告中明确的概念图：一致概念图
7. Graph Isomorphism for K_{3,3}-free and K_5-free graphs is in Log-space [O] . Datta Samir, Nimbhorkar Prajakta, Thierauf Thomas, 2009

机译：K_ {3,3} -free和K_5-free图的图同构在Log空间中
8. Classification and Enumeration of Minimum (d,3,3)-Graphs for Odd d. [R] . klee,victor 1976

机译：奇数d的最小（d，3,3） - 图的分类和枚举。

Reachability in K_(3,3)-Free Graphs and K_5-Free Graphs Is in Unambiguous Log-Space

摘要

著录项

相似文献

相关主题

期刊订阅