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
computational complexityhypergraphcombinatorial optimizationdegree sequencethreshold graphextremal combinatoric
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)
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