Isomorphism testing of k-trees is in NC, for fixed k
type: Item
instance of: scholarly article
title: Isomorphism testing of k-trees is in NC, for fixed k
zbMATH Open document ID: 0695.68031
DOI: 10.1016/0020-0190(90)90011-L
author: N. Chandrasekharan
published in: Information Processing Letters
publication date: 1990-01-01T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 4139285
zbMATH Keywords: parallel algorithms
zbMATH Keywords: computational complexity
zbMATH Keywords: CRCW PRAM
zbMATH Keywords: isomorphism
zbMATH Keywords: k- trees
MaRDI profile type: Publication
cites work: Properties and characterizations of k ‐trees
cites work: On acyclic simplicial complexes
cites work: Q4148000
cites work: Isomorphism Testing in Hookup Classes
cites work: A Linear Time Algorithm for Deciding Interval Graph Isomorphism
cites work: Isomorphism of graphs of bounded valence can be tested in polynomial time
cites work: On simple characterizations of k-trees
cites work: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
full work available at URL: 0020-0190(90)90011-l
OpenAlex ID: W1983937448
Recommended article: The Space Complexity of k-Tree Isomorphism
Recommended article: Q3798258
Recommended article: Subtree isomorphism is in random NC
Recommended article: Q5443620
Recommended article: The Isomorphism Problem for k-Trees Is Complete for Logspace
Recommended article: The isomorphism problem for \(k\)-trees is complete for logspace
Recommended article: On the complexity of finding iso- and other morphisms for partial \(k\)- trees
Recommended article: Fast parallel reordering and isomorphism testing of \(k\)-trees
Recommended article: An Improved Isomorphism Test for Bounded-tree-width Graphs
Recommended article: An improved isomorphism test for bounded-tree-width graphs
description: scientific article; zbMATH DE number 4139285