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

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic › peer review

42 Citaten (Scopus)

Samenvatting

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.

Originele taal-2	Engels
Pagina's (van-tot)	594-596
Tijdschrift	Operations Research Letters
Volume	36
Nummer van het tijdschrift	5
DOI's	https://doi.org/10.1016/j.orl.2008.05.004
Status	Gepubliceerd - 2008

Toegang tot document

10.1016/j.orl.2008.05.004

Citeer dit

@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

Samenvatting

Toegang tot document

Vingerafdruk

Citeer dit