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

DOI10.1016/j.orl.2008.05.004zbMath1210.90140MaRDI 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 complexity; combinatorial optimization; graph theory

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C60: Abstract computational complexity for mathematical programming problems

90C27: Combinatorial optimization

Related Items

NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs, Bottleneck Convex Subsets: Finding k Large Convex Sets in a Point Set, Degree realization by bipartite multigraphs, Filling crosswords is very hard, Complexity of splits reconstruction for low-degree trees, Burning number of caterpillars, NP-hardness of two edge cover generalizations with applications to control and bribery for approval voting, A note on the hardness of Skolem-type sequences, On the burning number of \(p\)-caterpillars, Relaxed and approximate graph realizations, 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, The complexity of degree anonymization by graph contractions, Burning a graph is hard, One-dimensional vehicle scheduling with a front-end depot and non-crossing constraints, Bottleneck convex subsets: finding \(k\) large convex sets in a point set, Complexity of Splits Reconstruction for Low-Degree Trees

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