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

combinatorial optimizationcomputational complexitygraph theory

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) 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

• Computing the bump number is easy
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• 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

(28)

• 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
• On degree sequence optimization
• Optimization over degree sequences of graphs
• Bottleneck convex subsets: finding k large convex sets in a point set
• Complexity of splits reconstruction for low-degree trees
• The Complexity of Metric Realization
• Parsimonious Multigraphs
• scientific article; zbMATH DE number 3993625 (Why is no real title available?)
• Complexity of splits reconstruction for low-degree trees
• Bottleneck Convex Subsets: Finding k Large Convex Sets in a Point Set
• Degree realization by bipartite multigraphs
• Filling crosswords is very hard
• Upper bounds and approximation results for the \(k\)-slow burning problem
• Tetris with few piece types
• On the role of the equal partition in degree realization by a bipartite graph
• Zero-sum partitions of abelian groups and their applications to magic- and antimagic-type labelings
• On bipartite graph realizations of a single degree sequence
• Broadcasting under structural restrictions
• Parameterized algorithms for the drone delivery problem
• 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

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)