An optimal lower bound on the number of variables for graph identification
type: Item
instance of: scholarly article
title: An optimal lower bound on the number of variables for graph identification
zbMATH Open document ID: 0785.68043
DOI: 10.1007/BF01305232
author: Martin Fürer
author: Jin-Yi Cai
author: Neil Immerman
published in: Combinatorica
publication date: 1993-03-10T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 03B10
zbMATH DE Number: 130620
zbMATH Keywords: graph identification
zbMATH Keywords: first-order logic with counting
zbMATH Keywords: Weisfeiler-Lehman method
describes a project that uses: nauty
MaRDI profile type: Publication
Wikidata QID: Q113847441
cites work: Q4091421
cites work: On the Complexity of Canonical Labeling of Strongly Regular Graphs
cites work: Q3912033
cites work: On the order of uniprimitive permutation groups
cites work: Random Graph Isomorphism
cites work: On uniformity within \(NC^ 1\)
cites work: 6-transitive graphs
cites work: Structure and complexity of relational queries
cites work: An application of games to the completeness problem for formalized theories
cites work: Coherent configurations. I: Ordinary representation theory
cites work: Number of quantifiers is better than number of tape cells
cites work: Upper and lower bounds for first order expressibility
cites work: Relational queries computable in polynomial time
cites work: Languages that Capture Complexity Classes
cites work: Definability with bounded number of bound variables
cites work: Isomorphism of graphs of bounded valence can be tested in polynomial time
cites work: A note on the graph isomorphism counting problem
cites work: The graph isomorphism disease
cites work: On construction and identification of graphs. With contributions by A. Lehman, G. M. Adelson-Velsky, V. Arlazarov, I. Faragev, A. Uskov, I. Zuev, M. Rosenfeld and B. Weisfeiler
cites work: Q3312272
full work available at URL: https://doi.org/10.1007/bf01305232
OpenAlex ID: W2181072414
Recommended article: A graph theoretical approach to the parameters identifiability characterisation
Recommended article: A probabilistic upper bound for the edge identification complexity of graphs
Recommended article: Identifiability for Graphexes and the Weak Kernel Metric
Recommended article: Parameter identifiability in a class of random graph mixture models
Recommended article: Graph signatures: identification and optimization
Recommended article: A comparison of approaches for finding minimum identifying codes on graphs
Recommended article: On the complexity of the identifiable subgraph problem, revisited
Recommended article: On the complexity of the identifiable subgraph problem
Recommended article: Extremal graphs for the identifying code problem
description: scientific article; zbMATH DE number 130620