University of Twente Student Theses
Computing certificates for the graph realization problem on 3-connected graphs
Speek, G.W. (2021) Computing certificates for the graph realization problem on 3-connected graphs.
|
PDF
880kB |
| Abstract: | For the graph realization problem we are given a binary matrix, and we need decide if there exists a graph that is represented by the given matrix. If such a graph can be found, that matrix is graphic. The already exist algorithms that determine the graphicness of matrices. In this paper we present an algorithm that can reduce a non-graphic matrix with the use of a 3-connected graph represented by some graphic submatrix of the given matrix. The output can be used as certificate to verify the non-graphicness and could give some insight as to why a given matrix is non-graphic. |
| Item Type: | Essay (Bachelor) |
| Faculty: | EEMCS: Electrical Engineering, Mathematics and Computer Science |
| Subject: | 31 mathematics |
| Programme: | Applied Mathematics BSc (56965) |
| Link to this item: | https://purl.utwente.nl/essays/86689 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page