Degree Sequence Optimization and Extremal Degree Enumerators
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913297330077696 |
|---|---|
| author | Onn, Shmuel |
| author_facet | Onn, Shmuel |
| contents | The degree sequence optimization problem is to find a subgraph of a given graph which maximizes the sum of given functions evaluated at the subgraph degrees. Here we study this problem by replacing degree sequences, via suitable nonlinear transformations, by suitable degree enumerators, and we introduce suitable degree enumerator polytopes.
We characterize their vertices, that is, the extremal degree enumerators, for complete graphs and some complete bipartite graphs, and use these characterizations to obtain simpler and faster algorithms for optimization over degree sequences for such graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_02551 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Degree Sequence Optimization and Extremal Degree Enumerators Onn, Shmuel Combinatorics Discrete Mathematics Data Structures and Algorithms Optimization and Control 05A, 15A, 51M, 52A, 52B, 52C, 62H, 68Q, 68R, 68U, 68W, 90B, 90C The degree sequence optimization problem is to find a subgraph of a given graph which maximizes the sum of given functions evaluated at the subgraph degrees. Here we study this problem by replacing degree sequences, via suitable nonlinear transformations, by suitable degree enumerators, and we introduce suitable degree enumerator polytopes. We characterize their vertices, that is, the extremal degree enumerators, for complete graphs and some complete bipartite graphs, and use these characterizations to obtain simpler and faster algorithms for optimization over degree sequences for such graphs. |
| title | Degree Sequence Optimization and Extremal Degree Enumerators |
| topic | Combinatorics Discrete Mathematics Data Structures and Algorithms Optimization and Control 05A, 15A, 51M, 52A, 52B, 52C, 62H, 68Q, 68R, 68U, 68W, 90B, 90C |
| url | https://arxiv.org/abs/2404.02551 |