A continuous characterization of the maximum vertex-weighted clique in hypergraphs

Qingsong Tang; Xiangde Zhang; Guoren Wang; Cheng Zhao

doi:10.1007/s10878-018-0259-9

A continuous characterization of the maximum vertex-weighted clique in hypergraphs

Qingsong Tang^*
, Xiangde Zhang
, Guoren Wang
, Cheng Zhao

^*Corresponding author for this work

Northeastern University China
School of Computer Science and Engineering
Indiana State University

Research output: Contribution to journal › Article › peer-review

Abstract

For a simple graph G on n vertices with adjacency matrix A, Motzkin and Strauss established a remarkable connection between the clique number and the global maximum value of the quadratic programm: max{ x^TAx} on the standard simplex: {∑i=1nxi=1,xi≥0}. In Gibbons et al. (Math Oper Res 122:754–768, 1997), an extension of the Motzkin–Straus formulation was provided for the vertex-weighted clique number of a graph. In this paper, we provide a continuous characterization of the maximum vertex-weighted clique problem for vertex-weighted uniform hypergraphs.

Original language	English
Pages (from-to)	1250-1260
Number of pages	11
Journal	Journal of Combinatorial Optimization
Volume	35
Issue number	4
DOIs	https://doi.org/10.1007/s10878-018-0259-9
Publication status	Published - 1 May 2018
Externally published	Yes

Keywords

Cliques of hypergraphs
Polynomial optimization
Vertex-weighted hypergraphs

Access to Document

10.1007/s10878-018-0259-9

Cite this

@article{ac48cde5f5a941d3a6ae1b72aca5dc00,

title = "A continuous characterization of the maximum vertex-weighted clique in hypergraphs",

abstract = "For a simple graph G on n vertices with adjacency matrix A, Motzkin and Strauss established a remarkable connection between the clique number and the global maximum value of the quadratic programm: max\{ xTAx\} on the standard simplex: \{∑i=1nxi=1,xi≥0\}. In Gibbons et al. (Math Oper Res 122:754–768, 1997), an extension of the Motzkin–Straus formulation was provided for the vertex-weighted clique number of a graph. In this paper, we provide a continuous characterization of the maximum vertex-weighted clique problem for vertex-weighted uniform hypergraphs.",

keywords = "Cliques of hypergraphs, Polynomial optimization, Vertex-weighted hypergraphs",

author = "Qingsong Tang and Xiangde Zhang and Guoren Wang and Cheng Zhao",

note = "Publisher Copyright: {\textcopyright} 2018, Springer Science+Business Media, LLC, part of Springer Nature.",

year = "2018",

month = may,

day = "1",

doi = "10.1007/s10878-018-0259-9",

language = "English",

volume = "35",

pages = "1250--1260",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "4",

}

TY - JOUR

T1 - A continuous characterization of the maximum vertex-weighted clique in hypergraphs

AU - Tang, Qingsong

AU - Zhang, Xiangde

AU - Wang, Guoren

AU - Zhao, Cheng

PY - 2018/5/1

Y1 - 2018/5/1

N2 - For a simple graph G on n vertices with adjacency matrix A, Motzkin and Strauss established a remarkable connection between the clique number and the global maximum value of the quadratic programm: max{ xTAx} on the standard simplex: {∑i=1nxi=1,xi≥0}. In Gibbons et al. (Math Oper Res 122:754–768, 1997), an extension of the Motzkin–Straus formulation was provided for the vertex-weighted clique number of a graph. In this paper, we provide a continuous characterization of the maximum vertex-weighted clique problem for vertex-weighted uniform hypergraphs.

AB - For a simple graph G on n vertices with adjacency matrix A, Motzkin and Strauss established a remarkable connection between the clique number and the global maximum value of the quadratic programm: max{ xTAx} on the standard simplex: {∑i=1nxi=1,xi≥0}. In Gibbons et al. (Math Oper Res 122:754–768, 1997), an extension of the Motzkin–Straus formulation was provided for the vertex-weighted clique number of a graph. In this paper, we provide a continuous characterization of the maximum vertex-weighted clique problem for vertex-weighted uniform hypergraphs.

KW - Cliques of hypergraphs

KW - Polynomial optimization

KW - Vertex-weighted hypergraphs

UR - https://www.scopus.com/pages/publications/85042447981

U2 - 10.1007/s10878-018-0259-9

DO - 10.1007/s10878-018-0259-9

M3 - Article

AN - SCOPUS:85042447981

SN - 1382-6905

VL - 35

SP - 1250

EP - 1260

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 4

ER -

A continuous characterization of the maximum vertex-weighted clique in hypergraphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this