Multigraph realizations of degree sequences: Maximization is easy, minimization is hard
From MaRDI portal
Publication:957360
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
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