Graph Isomorphism for K_{3,3}-free and K_5-free graphs is in Log-space

Samir Datta; Prajakta Nimbhorkar; Thomas Thierauf; Fabian Wagner

首页> 外文期刊>LIPIcs : Leibniz International Proceedings in Informatics >Graph Isomorphism for K_{3,3}-free and K_5-free graphs is in Log-space

【24h】

Graph Isomorphism for K_{3,3}-free and K_5-free graphs is in Log-space

机译：无K_ {3,3}和无K_5图的图同构在对数空间中

获取原文

获取外文期刊封面封底 >>

开具论文收录证明 >>

文献代查 >>

页面导航

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

摘要

Graph isomorphism is an important and widely studied computational problem with a yet unsettled complexity. However, the exact complexity is known for isomorphism of various classes of graphs. Recently, cite{DLNTW09} proved that planar isomorphism is com

机译：图同构是一个重要且经过广泛研究的计算问题，但尚未解决。但是，已知各种图的同构的确切复杂度。最近， cite {DLNTW09}证明平面同构是com

著录项

来源
《LIPIcs : Leibniz International Proceedings in Informatics》 |2009年第2期|共12页
作者
Samir Datta; Prajakta Nimbhorkar; Thomas Thierauf; Fabian Wagner;
展开▼
作者单位

展开▼
收录信息
原文格式 PDF
正文语种
中图分类计算技术、计算机技术;
关键词

相似文献

外文文献
中文文献
专利

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. Efficient Approximation Schemes for Maximization Problems on K_(3,3)-free or K_5-free Graphs [J] . Zhi-Zhong Chen Journal of Algorithms . 1998,第1期

机译：无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 Fundamentals of computation theory . 2009

机译：无K_（3,3）图和K_5无图的可达性在明确的日志空间中
5. Computable Isomorphisms of Directed Graphs and Trees [D] . Walker, Hakim J. 2017

机译：可计行的图形和树木的同构
6. Understanding Graph Isomorphism Network for rs-fMRI Functional Connectivity Analysis [O] . Byung-Hoon Kim, Jong Chul Ye 2020

机译：了解RS-FMRI功能连接分析的图形同构网络
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. Isomorphisms and Non-Isomorphisms of Graph Models [R] . Schellinx, H. 1990

机译：图模型的同构和非同构

Graph Isomorphism for K_{3,3}-free and K_5-free graphs is in Log-space

摘要

著录项

相似文献

相关主题

期刊订阅