Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 3 of 3
Full-Text Articles in Physical Sciences and Mathematics
An Efficient Algorithm To Test Potential Bipartiteness Of Graphical Degree Sequences, Kai Wang
An Efficient Algorithm To Test Potential Bipartiteness Of Graphical Degree Sequences, Kai Wang
Theory and Applications of Graphs
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.
Forcibly-Biconnected Graphical Degree Sequences: Decision Algorithms And Enumerative Results, Kai Wang
Forcibly-Biconnected Graphical Degree Sequences: Decision Algorithms And Enumerative Results, Kai Wang
Theory and Applications of Graphs
We present an algorithm to test whether a given graphical degree sequence is forcibly biconnected. The worst case time complexity of the algorithm is shown to be exponential but it is still much better than the previous basic algorithm for this problem. We show through experimental evaluations that the algorithm is efficient on average. We also adapt the classic algorithm of Ruskey et al. and that of Barnes and Savage to obtain some enumerative results about forcibly biconnected graphical degree sequences of given length n and forcibly biconnected graphical partitions of given even integer n. Based on these enumerative …
An Efficient Algorithm To Test Forcibly-Connectedness Of Graphical Degree Sequences, Kai Wang
An Efficient Algorithm To Test Forcibly-Connectedness Of Graphical Degree Sequences, Kai Wang
Theory and Applications of Graphs
We present an algorithm to test whether a given graphical degree sequence is forcibly connected or not and prove its correctness. We also outline the extensions of the algorithm to test whether a given graphical degree sequence is forcibly k-connected or not for every fixed k ≥ 2. We show through experimental evaluations that the algorithm is efficient on average, though its worst case run time is probably exponential. We also adapt Ruskey et al's classic algorithm to enumerate zero-free graphical degree sequences of length n and Barnes and Savage's classic algorithm to enumerate graphical partitions of even integer …