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

DOI10.1016/j.orl.2008.05.004zbMath1210.90140OpenAlexW2050404755MaRDI QIDQ957360

Gerhard J. Woeginger, Todd G. Will, Heather Hulett

Publication date: 27 November 2008

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2008.05.004

zbMATH Keywords

computational complexitycombinatorial optimizationgraph theory

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items (17)

The complexity of degree anonymization by graph contractions ⋮ Burning a graph is hard ⋮ NP-hardness of two edge cover generalizations with applications to control and bribery for approval voting ⋮ Bottleneck Convex Subsets: Finding k Large Convex Sets in a Point Set ⋮ Degree realization by bipartite multigraphs ⋮ Filling crosswords is very hard ⋮ Bottleneck convex subsets: finding \(k\) large convex sets in a point set ⋮ Complexity of splits reconstruction for low-degree trees ⋮ One-dimensional vehicle scheduling with a front-end depot and non-crossing constraints ⋮ A 5-parameter complexity classification of the two-stage flow shop scheduling problem with job dependent storage requirements ⋮ The piggyback transportation problem: transporting drones launched from a flying warehouse ⋮ A note on the hardness of Skolem-type sequences ⋮ NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs ⋮ On the burning number of \(p\)-caterpillars ⋮ Complexity of Splits Reconstruction for Low-Degree Trees ⋮ Burning number of caterpillars ⋮ Relaxed and approximate graph realizations

Cites Work

• Unnamed Item
• The complexity of completing partial Latin squares
• Computing the bump number is easy
• Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard
• The geometric maximum traveling salesman problem
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
• Parsimonious Multigraphs
• On Determining Minimal Singularities for the Realizations of an Incidence Sequence
• Minimal Number of Multiple Edges in Realization of an Incidence Sequence Without Loops

This page was built for publication: Multigraph realizations of degree sequences: Maximization is easy, minimization is hard