Fast algorithms for computing the characteristic polynomial of threshold and chain graphs
| Autor: | Slobodan K. Simić, Dejan Živković, Edin Dolicanin, Milica Anđelić |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Threshold graph
Divisor Computer science Efficient algorithm Applied Mathematics 0211 other engineering and technologies Structure (category theory) 021107 urban & regional planning 0102 computer and information sciences 02 engineering and technology 01 natural sciences Graph Computational Mathematics Chain (algebraic topology) 010201 computation theory & mathematics ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION Adjacency matrix Algorithm MathematicsofComputing_DISCRETEMATHEMATICS Characteristic polynomial |
| Zdroj: | Applied Mathematics and Computation. 332:329-337 |
| ISSN: | 0096-3003 |
| DOI: | 10.1016/j.amc.2018.03.024 |
| Popis: | The characteristic polynomial of a graph is the characteristic polynomial of its adjacency matrix. Finding efficient algorithms for computing characteristic polynomial of graphs is an active area of research and for some graph classes, like threshold graphs, there exist very fast algorithms which exploit combinatorial structure of the graphs. In this paper, we put forward some novel ideas based on divisor technique to obtain fast algorithms for computing the characteristic polynomial of threshold and chain graphs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect