Tight bounds for finding degrees from the adjacency matrix

DOI10.1007/3-540-59175-3_80zbMath1495.68161OpenAlexW1544697331MaRDI QIDQ5096323

R. Balasubramanian, Venkatesh Raman, G. Srinivasaraghavan

Publication date: 16 August 2022

Published in: LATIN '95: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-59175-3_80

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Cites Work

• Unnamed Item
• Unnamed Item
• An optimal algorithm for sink-finding
• On recognizing graph properties from adjacency matrices
• The complexity of finding generalized paths in tournaments
• Monotone Bipartite Graph Properties are Evasive
• Sorting, Minimal Feedback Sets, and Hamilton Paths in Tournaments
• The complexity of finding certain trees in tournaments

This page was built for publication: Tight bounds for finding degrees from the adjacency matrix