A lower bound for the recognition of digraph properties

DOI10.1007/BF02122695zbMath0733.05041OpenAlexW1980974491MaRDI QIDQ810043

Valerie King

Publication date: 1990

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02122695

zbMATH Keywords

complexitydigraphadjacency matrix

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Directed graphs (digraphs), tournaments (05C20)

Related Items (6)

On the recognition complexity of some graph properties ⋮ Elusiveness of finding degrees ⋮ Elusiveness of Finding Degrees ⋮ An asymptotic bound for the complexity of monotone graph properties ⋮ Embedding Graphs into Larger Graphs: Results, Methods, and Problems ⋮ On the elusiveness of Hamiltonian property

Cites Work

• Unnamed Item
• A topological approach to evasiveness
• Fixed-point sets of group actions on finite acyclic complexes
• Further results on the Aanderaa-Rosenberg conjecture
• On recognizing graph properties from adjacency matrices
• Monotone Bipartite Graph Properties are Evasive
• Fixed-Point Theorems for Periodic Transformations

This page was built for publication: A lower bound for the recognition of digraph properties