Efficient Computation of the Characteristic Polynomial of a Threshold Graph

DOI10.1007/978-3-319-19647-3_5zbMath1410.05094arXiv1503.00617OpenAlexW2615740192MaRDI QIDQ3452551

Martin Fuerer

Publication date: 12 November 2015

Published in: Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1503.00617

zbMATH Keywords

characteristic polynomialefficient algorithmsthreshold graphs

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph polynomials (05C31) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

Fast algorithms for computing the characteristic polynomial of threshold and chain graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient computation of the characteristic polynomial of a tree and related tasks
• Matrix multiplication via arithmetic progressions
• Computing the characteristic polynomial of a tree
• Fast algorithms for the characteristic polynomial
• Threshold graphs and related topics
• Fast multiplication of large numbers
• Computing the Characteristic Polynomial of Threshold Graphs
• Faster Integer Multiplication
• A Graph-Theoretic Characterization of the $\text{PV}_{\text{chunk}}$ Class of Synchronizing Primitives
• Reducing the adjacency matrix of a tree

This page was built for publication: Efficient Computation of the Characteristic Polynomial of a Threshold Graph