Efficient computation of the characteristic polynomial of a threshold graph

DOI10.1016/J.TCS.2016.07.013MaRDI QIDQ507427zbMATH OpenOpenAlexFDO

Authors Martin Fürer

Publication date 6 February 2017

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

Full work available at URL https://doi.org/10.1016/j.tcs.2016.07.013

zbMATH Keywords

characteristic polynomialefficient algorithmsthreshold graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph polynomials (05C31)

Recommendations

• Efficient computation of the characteristic polynomial of a threshold graph
• Computing the characteristic polynomial of threshold graphs
• Fast algorithms for computing the characteristic polynomial of threshold and chain graphs
• No threshold graphs are cospectral
• Efficient Computation of the Characteristic Polynomial of a Tree and Related Tasks

Cites work

• scientific article; zbMATH DE number 3856407 (Why is no real title available?)
• scientific article; zbMATH DE number 5177331 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3598234 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• A Graph-Theoretic Characterization of the $\text{PV}_{\text{chunk}}$ Class of Synchronizing Primitives
• Computing the characteristic polynomial of a tree
• Computing the characteristic polynomial of threshold graphs
• Connected graphs of fixed order and size with maximal index: some spectral bounds
• Efficient computation of the characteristic polynomial of a tree and related tasks
• Eigenvalue location in threshold graphs
• Fast algorithms for the characteristic polynomial
• Fast multiplication of large numbers
• Faster algorithms for the characteristic polynomial
• Faster integer multiplication
• Improved bound for complexity of matrix multiplication
• Matrix multiplication via arithmetic progressions
• Modern computer algebra
• Multiplying matrices faster than coppersmith-winograd
• On certain eigenspaces of cographs
• On fast multiplication of polynomials over arbitrary algebras
• On nested split graphs whose second largest eigenvalue is less than 1
• On the adjacency matrix of a threshold graph
• On the complexity of computing determinants
• Powers of tensors and fast matrix multiplication
• Reducing the adjacency matrix of a tree
• The rank of a cograph
• Threshold graphs and related topics

Cited in

(10)

• Efficient deterministic approximate counting for low-degree polynomial threshold functions
• Efficient computation of the characteristic polynomial of a threshold graph
• Graph-Theoretic Concepts in Computer Science
• No threshold graphs are cospectral
• Delta invariant for Eulerian digraphs
• An explicit formula for the distance characteristic polynomial of threshold graphs
• Computing the characteristic polynomial of threshold graphs
• A method to calculate the characteristic polynomials of a graph on \(n\) vertices by the aid of a computer
• The role of the anti-regular graph in the spectral analysis of threshold graphs
• Fast algorithms for computing the characteristic polynomial of threshold and chain graphs

This page was built for publication: Efficient computation of the characteristic polynomial of a threshold graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q507427)