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

DOI10.1016/J.ORL.2008.05.004MaRDI QIDQ957360zbMATH OpenOpenAlexFDO

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

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) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Publication:4722101
• Parsimonious Multigraphs
• Hypergraphic degree sequences are hard
• Some NP-complete problems for hypergraph degree sequences
• The Complexity of Metric Realization

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Computing the bump number is easy
• Minimal Number of Multiple Edges in Realization of an Incidence Sequence Without Loops
• Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard
• On Determining Minimal Singularities for the Realizations of an Incidence Sequence
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
• Parsimonious Multigraphs
• The complexity of completing partial Latin squares
• The geometric maximum traveling salesman problem

Cited in

(21)

• Bottleneck Convex Subsets: Finding k Large Convex Sets in a Point Set
• One-dimensional vehicle scheduling with a front-end depot and non-crossing constraints
• A note on the hardness of Skolem-type sequences
• Relaxed and approximate graph realizations
• The complexity of degree anonymization by graph contractions
• scientific article; zbMATH DE number 3993625 (Why is no real title available?)
• A 5-parameter complexity classification of the two-stage flow shop scheduling problem with job dependent storage requirements
• Optimization over degree sequences of graphs
• Degree realization by bipartite multigraphs
• NP-hardness of two edge cover generalizations with applications to control and bribery for approval voting
• Filling crosswords is very hard
• Complexity of splits reconstruction for low-degree trees
• Complexity of splits reconstruction for low-degree trees
• The piggyback transportation problem: transporting drones launched from a flying warehouse
• Burning number of caterpillars
• Burning a graph is hard
• Parsimonious Multigraphs
• Bottleneck convex subsets: finding \(k\) large convex sets in a point set
• Upper bounds and approximation results for the \(k\)-slow burning problem
• The Complexity of Metric Realization
• On the burning number of \(p\)-caterpillars

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q957360)