An efficient algorithm to test potential bipartiteness of graphical degree sequences

DOI10.20429/TAG.2021.080103zbMATH Open1462.05340arXiv1908.06821OpenAlexW3138955544MaRDI QIDQ4987152FDOQ4987152

Authors:

Publication date: 28 April 2021

Published in: Theory and Applications of Graphs (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

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

zbMATH Keywords

graphical degree sequencebipartite realization

Mathematics Subject Classification ID

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

Cited In (7)

• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• An algebraic Monte-Carlo algorithm for the partition adjacency matrix realization problem
• Forcibly-biconnected Graphical Degree Sequences: Decision Algorithms and Enumerative Results

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)