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

被引：29

作者：

Hulett, Heather ^{[2
]}

Will, Todd G. ^{[2
]}

Woeginger, Gerhard J. ^{[1
]}

机构：

[1] Tech Univ Eindhoven, Dept Math & Comp Sci, NL-5600 MB Eindhoven, Netherlands

[2] Univ Wisconsin, Dept Math, La Crosse, WI 54601 USA

来源：

OPERATIONS RESEARCH LETTERS | 2008年 / 36卷 / 05期

关键词：

Computational complexity; Combinatorial optimization; Graph theory;

D O I：

10.1016/j.orl.2008.05.004

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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. (c) 2008 Elsevier B.V. All rights reserved.

引用

页码：594 / 596

页数：3

共 10 条

[1] The geometric maximum traveling salesman problem [J].

Barvinok, A ;

Fekete, SP ;

Johnson, DS ;

Tamir, A ;

Woeginger, GJ ;

Woodroofe, R .

JOURNAL OF THE ACM, 2003, 50 (05) :641-664

[2] THE COMPLEXITY OF COMPLETING PARTIAL LATIN SQUARES [J].

COLBOURN, CJ .

DISCRETE APPLIED MATHEMATICS, 1984, 8 (01) :25-30

[3]

Garey MR, 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[4] COMPUTING THE BUMP NUMBER IS EASY [J].

HABIB, M ;

MOHRING, RH ;

STEINER, G .

ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 1988, 5 (02) :107-129

[5] ON REALIZABILITY OF A SET OF INTEGERS AS DEGREES OF THE VERTICES OF A LINEAR GRAPH .1. [J].

HAKIMI, SL .

JOURNAL OF THE SOCIETY FOR INDUSTRIAL AND APPLIED MATHEMATICS, 1962, 10 (03) :496-506

[6] MINIMAL NUMBER OF MULTIPLE EDGES IN REALIZATION OF AN INCIDENCE SEQUENCE WITHOUT LOOPS [J].

KLEITMAN, DJ .

SIAM JOURNAL ON APPLIED MATHEMATICS, 1970, 18 (01) :25-&

[7] THE COMPLEXITY OF SEGMENTED CHANNEL ROUTING [J].

LI, WN .

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 1995, 14 (04) :518-523

[8]

OWENS B, 1967, SIAM J APPL MATH MAT, V15, P406

[9] Parsimonious multigraphs [J].

Will, TG ;

Hulett, H .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2004, 18 (02) :241-245

[10] Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard [J].

Yu, WC ;

Hoogeveen, H ;

Lenstra, JK .

JOURNAL OF SCHEDULING, 2004, 7 (05) :333-348

← 1 →