Optimization over Degree Sequences

DOI10.1137/17M1134482zbMath1392.05083arXiv1706.03951OpenAlexW2963692782MaRDI QIDQ4579955

Antoine Deza, Shmuel Onn, Asaf Levin, Syed M. Meesum

Publication date: 10 August 2018

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1706.03951

zbMATH Keywords

computational complexityhypergraphcombinatorial optimizationdegree sequencethreshold graphextremal combinatoric

Mathematics Subject Classification ID

Hypergraphs (05C65) Combinatorial optimization (90C27) Extremal set theory (05D05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex degrees (05C07)

Related Items (16)

New sufficient conditions on the degree sequences of uniform hypergraphs ⋮ On degree sequence optimization ⋮ Optimization over degree sequences of graphs ⋮ On the reconstruction of 3-uniform hypergraphs from degree sequences of span-two ⋮ Degree sequence optimization in bounded treewidth ⋮ Characterization and reconstruction of hypergraphic pattern sequences ⋮ Structure and complexity of 2-intersection graphs of 3-hypergraphs ⋮ Separable and equatable hypergraphs ⋮ On line sum optimization ⋮ On null 3-hypergraphs ⋮ Uniform and monotone line sum optimization ⋮ Properties of unique degree sequences of 3-uniform hypergraphs ⋮ On the reconstruction of 3-uniform hypergraphs from step-two degree sequences ⋮ On the Degree Sequence of 3-Uniform Hypergraph: A New Sufficient Condition ⋮ Combinatorial properties of degree sequences of 3-uniform hypergraphs arising from Saind arrays ⋮ A study on the existence of null labelling for 3-hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The polytope of degree sequences
• Shifted set families, degree sequences, and plethysm
• Some NP-complete problems for hypergraph degree sequences
• Geometric algorithms and combinatorial optimization.
• The polytope of degree sequences of hypergraphs
• Shifted matroid optimization
• The unimodular intersection problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Threshold graphs and related topics
• Nonconvexity of the set of hypergraph degree sequences
• Extreme degree sequences of simple graphs
• Approximate separable multichoice optimization over monotone systems
• A remark on the existence of finite graphs
• Combinatorial Properties of Matrices of Zeros and Ones
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
• Degree multisets of hypergraphs
• On the Swap-Distances of Different Realizations of a Graphical Degree Sequence
• A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
• Parameterized shifted combinatorial optimization

This page was built for publication: Optimization over Degree Sequences