On recognizing graph properties from adjacency matrices

DOI10.1016/0304-3975(76)90053-0zbMath0358.68079OpenAlexW2016606569MaRDI QIDQ1238421

Publication date: 1977

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(76)90053-0

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Algorithms in computer science (68W99)

Related Items

Exact lower time bounds for computing Boolean functions on CREW PRAMs ⋮ Counting induced subgraphs: an algebraic approach to \(\#\)W[1-hardness] ⋮ On lattices with Möbius function \(\pm 1,0\) ⋮ A fast algorithm for translating combinator expressions with BC-chains ⋮ Block sensitivity of weakly symmetric functions ⋮ Totally optimal decision trees for Boolean functions ⋮ Generalized adjacency and Laplacian spectra of the weighted corona graphs ⋮ A class of algorithms which require nonlinear time to maintain disjoint sets ⋮ On the recognition complexity of some graph properties ⋮ Tight bounds for finding degrees from the adjacency matrix ⋮ A hierarchy of dismantlings in graphs ⋮ Evasiveness through binary decision diagrams ⋮ Query complexity of tournament solutions ⋮ Discovery of Network Properties with All-Shortest-Paths Queries ⋮ Discrete extremal problems ⋮ Elusiveness of finding degrees ⋮ Using Brouwer’s Fixed Point Theorem ⋮ Unnamed Item ⋮ Transitive q-Ary Functions over Finite Fields or Finite Sets: Counts, Properties and Applications ⋮ Elusiveness of Finding Degrees ⋮ Adaptive majority problems for restricted query graphs and for weighted sets ⋮ Separation Between Deterministic and Randomized Query Complexity ⋮ Nontrivial monotone weakly symmetric Boolean functions with six variables are elusive ⋮ An asymptotic bound for the complexity of monotone graph properties ⋮ An \(\Omega{} (n^{5/4})\) lower bound on the randomized complexity of graph properties ⋮ On computing majority by comparisons ⋮ Unnamed Item ⋮ Discovery of network properties with all-shortest-paths queries ⋮ On the elusiveness of Hamiltonian property ⋮ On read-once threshold formulae and their randomized decision tree complexity ⋮ A note on the query complexity of the Condorcet winner problem ⋮ Block sensitivity of minterm-transitive functions ⋮ Properties of complexity measures for PRAMs and WRAMs ⋮ Unnamed Item ⋮ Further results on the Aanderaa-Rosenberg conjecture ⋮ The computational complexity of matroid properties ⋮ On the relationship between energy complexity and other Boolean function measures ⋮ A generalized model for understanding evasiveness ⋮ Delta invariant for Eulerian digraphs ⋮ The Rivest-Vuillemin conjecture on monotone Boolean functions is true for ten variables ⋮ Counting induced subgraphs: a topological approach to \#W[1-hardness] ⋮ Some results related to the evasiveness conjecture. ⋮ The critical complexity of graph properties ⋮ Complexity measures and decision tree complexity: a survey. ⋮ Combinatorial analysis (nonnegative matrices, algorithmic problems) ⋮ Communication complexity and combinatorial lattice theory ⋮ A topological approach to evasiveness ⋮ Any monotone property of 3-uniform hypergraphs is weakly evasive ⋮ Lower bounds to randomized algorithms for graph properties ⋮ A lower bound for the recognition of digraph properties

Cites Work