The (maximum) independent set problem (MISP) on Riemannian manifolds of higher dimensions

Notes, id: notes_000X

Abstract

We consider the determination of (maximum) independent sets of arbitrary graphs with the help of higher dimensional tensor based representations and subgraph decomposition by weighted based introduction of virtual edges. Finally, we do a comparison of our algorithm with a similiar one given by Tarjan in Decomposition by clique separators. In contrast to Tarjan's algorithm, we propose an algorithm which offers the possibility to choose the atom subgraphs freely instead of handling mandatory atom subgraphs given by a decomposition.

Documents

• notes-MISRiemannian.pdf: The final LaTeX document
• notes_Zoebelein.pdf: Original handwritten version of the document
• oldSpringNotes_Zoebelein.pdf: First handwritten notes from spring 2020 considering the topic

License

See License file.