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

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

Research output: Contribution to journalArticleAcademicpeer-review

27 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 languageEnglish
Pages (from-to)594-596
JournalOperations Research Letters
Volume36
Issue number5
DOIs
Publication statusPublished - 2008

Fingerprint

Dive into the research topics of 'Multigraph realizations of degree sequences : Maximization is easy, minimization is hard'. Together they form a unique fingerprint.

Cite this