An efficient algorithm to test potential bipartiteness of graphical degree sequences

DOI10.20429/TAG.2021.080103MaRDI QIDQ4987152zbMATH OpenOpenAlexFDO

Authors

Publication date 28 April 2021

Published in Theory and Applications of Graphs (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1908.06821

zbMATH Keywords

graphical degree sequencebipartite realization

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex degrees (05C07)

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.

Recommendations

• scientific article; zbMATH DE number 1294016
• scientific article; zbMATH DE number 1775414
• Sampling \(k\)-partite graphs with a given degree sequence
• Constructing a bipartite graph of maximum connectivity with prescribed degrees
• Rejection sampling of bipartite graphs with given degree sequence

Cited in

(7)

• Forcibly-biconnected Graphical Degree Sequences: Decision Algorithms and Enumerative Results
• scientific article; zbMATH DE number 1775414 (Why is no real title available?)
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• scientific article; zbMATH DE number 1522753 (Why is no real title available?)
• scientific article; zbMATH DE number 1796979 (Why is no real title available?)
• An algebraic Monte-Carlo algorithm for the partition adjacency matrix realization problem
• scientific article; zbMATH DE number 5863491 (Why is no real title available?)

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)