Multigraph realizations of degree sequences : Maximization is easy, minimization is hard

H. Hulett; T.G. Will; G.J. Woeginger

doi:10.1016/j.orl.2008.05.004

Multigraph realizations of degree sequences : Maximization is easy, minimization is hard

H. Hulett
, T.G. Will
, G.J. Woeginger

Combinatorial Optimization

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

50 Citations (Scopus)

Abstract

The following minimization problem is shown to be NP-hard: Given a graphic degree sequence, find a realization of this degree sequence as loopless multigraph that minimizes the number of edges in the underlying support graph. The corresponding maximization problem is known to be solvable in polynomial time.

Original language	English
Pages (from-to)	594-596
Journal	Operations Research Letters
Volume	36
Issue number	5
DOIs	https://doi.org/10.1016/j.orl.2008.05.004
Publication status	Published - 2008

Access to Document

10.1016/j.orl.2008.05.004

Cite this

@article{443c6b320d164351bccc21579f5ae37e,

title = "Multigraph realizations of degree sequences : Maximization is easy, minimization is hard",

abstract = "The following minimization problem is shown to be NP-hard: Given a graphic degree sequence, find a realization of this degree sequence as loopless multigraph that minimizes the number of edges in the underlying support graph. The corresponding maximization problem is known to be solvable in polynomial time.",

author = "H. Hulett and T.G. Will and G.J. Woeginger",

year = "2008",

doi = "10.1016/j.orl.2008.05.004",

language = "English",

volume = "36",

pages = "594--596",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

T1 - Multigraph realizations of degree sequences : Maximization is easy, minimization is hard

AU - Hulett, H.

AU - Will, T.G.

AU - Woeginger, G.J.

PY - 2008

Y1 - 2008

N2 - The following minimization problem is shown to be NP-hard: Given a graphic degree sequence, find a realization of this degree sequence as loopless multigraph that minimizes the number of edges in the underlying support graph. The corresponding maximization problem is known to be solvable in polynomial time.

AB - The following minimization problem is shown to be NP-hard: Given a graphic degree sequence, find a realization of this degree sequence as loopless multigraph that minimizes the number of edges in the underlying support graph. The corresponding maximization problem is known to be solvable in polynomial time.

U2 - 10.1016/j.orl.2008.05.004

DO - 10.1016/j.orl.2008.05.004

M3 - Article

SN - 0167-6377

VL - 36

SP - 594

EP - 596

JO - Operations Research Letters

JF - Operations Research Letters

IS - 5

ER -

Multigraph realizations of degree sequences : Maximization is easy, minimization is hard

Abstract

Access to Document

Fingerprint

Cite this