An Efficient Algorithm to Test Potential Bipartiteness of Graphical Degree Sequences
From MaRDI portal
Publication:4987152
DOI10.20429/TAG.2021.080103zbMATH Open1462.05340arXiv1908.06821OpenAlexW3138955544MaRDI QIDQ4987152
Author name not available (Why is that?)
Publication date: 28 April 2021
Published in: (Search for Journal in Brave)
Abstract: As a partial answer to a question of Rao, a deterministic and customizable efficient algorithm is presented to test whether an arbitrary graphical degree sequence has a bipartite realization. The algorithm can be configured to run in polynomial time, at the expense of possibly producing an erroneous output on some "yes" instances but with very low error rate.
Full work available at URL: https://arxiv.org/abs/1908.06821
No records found.
No records found.
This page was built for publication: An Efficient Algorithm to Test Potential Bipartiteness of Graphical Degree Sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4987152)
