An efficient algorithm to test potential bipartiteness of graphical degree sequences

Kai Wang

doi:10.20429/TAG.2021.080103

An efficient algorithm to test potential bipartiteness of graphical degree sequences

Kai Wang

Computer Science

Georgia Southern University

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Pages (from-to)	1-13
Number of pages	13
Journal	Theory and Applications of Graphs
Volume	8
Issue number	1
DOIs	https://doi.org/10.20429/TAG.2021.080103
State	Published - Mar 2021

Scopus Subject Areas

Theoretical Computer Science
Numerical Analysis
Discrete Mathematics and Combinatorics

Keywords

— graphical degree sequence, bipartite realization

Access to Document

10.20429/TAG.2021.080103

Cite this

@article{0ee628dba92f44ef8ffe4518df7e80a6,

title = "An efficient algorithm to test potential bipartiteness of graphical degree sequences",

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.",

keywords = "— graphical degree sequence, bipartite realization",

author = "Kai Wang",

note = "Publisher Copyright: {\textcopyright} 2021 The Author(s).",

year = "2021",

month = mar,

doi = "10.20429/TAG.2021.080103",

language = "English",

volume = "8",

pages = "1--13",

journal = "Theory and Applications of Graphs",

issn = "2470-9859",

publisher = "Georgia Southern University",

number = "1",

}

TY - JOUR

T1 - An efficient algorithm to test potential bipartiteness of graphical degree sequences

AU - Wang, Kai

PY - 2021/3

Y1 - 2021/3

N2 - 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.

AB - 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.

KW - — graphical degree sequence, bipartite realization

UR - http://www.scopus.com/inward/record.url?scp=85104467336&partnerID=8YFLogxK

U2 - 10.20429/TAG.2021.080103

DO - 10.20429/TAG.2021.080103

M3 - Article

AN - SCOPUS:85104467336

SN - 2470-9859

VL - 8

SP - 1

EP - 13

JO - Theory and Applications of Graphs

JF - Theory and Applications of Graphs

IS - 1

ER -

An efficient algorithm to test potential bipartiteness of graphical degree sequences

Abstract

Scopus Subject Areas

Keywords

Access to Document

Other files and links

Fingerprint

Cite this