An Efficient Algorithm to Test Potentially Bipartiteness of Graphical Degree Sequences
作者： Kai Wang
DOI:
关键词:
摘要: As a partial answer to question of Rao, deterministic and customizable efficient algorithm is presented test whether an arbitrary graphical degree sequence has bipartite realization. The can be configured run in polynomial time, at the expense possibly producing erroneous output on some "yes" instances but with very low error rate.
arxiv.org参考文章(8)
S. B. Rao, A survey of the theory of potentially P-graphic and forcibly P-graphic degree sequences Combinatorics and Graph Theory. pp. 417- 440 ,(1981) , 10.1007/BFB0092288
O. Favaron, M. Mahéo, J.-F. Saclé, On the residue of a graph Journal of Graph Theory. ,vol. 15, pp. 39- 64 ,(1991) , 10.1002/JGT.3190150107
Narong Punnim, Degree Sequences and Chromatic Numbers of Graphs Graphs and Combinatorics. ,vol. 18, pp. 597- 603 ,(2002) , 10.1007/S003730200044
Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness ,(1979)
Owen Murphy, Lower bounds on the stability number of graphs computed in terms of degrees Discrete Mathematics. ,vol. 90, pp. 207- 211 ,(1991) , 10.1016/0012-365X(91)90357-8
Ian Holyer, The NP-Completeness of Edge-Coloring SIAM Journal on Computing. ,vol. 10, pp. 718- 720 ,(1981) , 10.1137/0210055
Paul Erdős, Robin J Wilson, On the chromatic index of almost all graphs Journal of Combinatorial Theory, Series B. ,vol. 23, pp. 255- 257 ,(1977) , 10.1016/0095-8956(77)90039-9
Konstantinos Koiliaris, Chao Xu, Faster Pseudopolynomial Time Algorithms for Subset Sum ACM Transactions on Algorithms. ,vol. 15, pp. 1- 20 ,(2019) , 10.1145/3329863