Concept
Vertex cover in hypergraphs
Related publications (25)
Molecular hypergraph neural networks
Philippe Schwaller, Junwu Chen
Graph neural networks (GNNs) have demonstrated promising performance across various chemistry-related tasks. However, conventional graphs only model the pairwise connectivity in molecules, failing to adequately represent higher order connections, such as m ...
Aip Publishing2024Hypergraph-Based Fast Distributed AC Power Flow Optimization
Colin Neil Jones, Yuning Jiang, Yingzhao Lian, Xinliang Dai
This paper presents a novel distributed approach for solving AC power flow (PF) problems. The optimization problem is reformulated into a distributed form using a communication structure corresponding to a hypergraph, by which complex relationships between ...
New York2023Motif Cut Sparsifiers
Mikhail Kapralov, Mikhail Makarov, Jakab Tardos
A motif is a frequently occurring subgraph of a given directed or undirected graph G (Milo et al.). Motifs capture higher order organizational structure of G beyond edge relationships, and, therefore, have found wide applications such as in graph clusterin ...
IEEE COMPUTER SOC2022Random walks and forbidden minors III: poly(d epsilon(-1))-time partition oracles for minor-free graph classes
Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs in these classes have hyperfinite decompositions, where, one removes a small ...
IEEE COMPUTER SOC2022Space-Efficient Representations of Graphs
With the increasing prevalence of massive datasets, it becomes important to design algorithmic techniques for dealing with scenarios where the input to be processed does not fit in the memory of a single machine. Many highly successful approaches have emer ...
EPFL2022Towards Tight Bounds for Spectral Sparsification of Hypergraphs
Mikhail Kapralov, Jakab Tardos
Cut and spectral sparsification of graphs have numerous applications, including e.g. speeding up algorithms for cuts and Laplacian solvers. These powerful notions have recently been extended to hypergraphs, which are much richer and may offer new applicati ...
ASSOC COMPUTING MACHINERY2021On subgraphs of C-2k-free graphs and a problem of Kuhn and Osthus
Let c denote the largest constant such that every C-6-free graph G contains a bipartite and C-4-free subgraph having a fraction c of edges of G. Gyori, Kensell and Tompkins showed that 3/8
2020Asyrnptotics for the Turan number of Berge-K-2,K-t
Let F be a graph. A hypergraph is called Berge-F if it can be obtained by replacing each edge in F by a hyperedge containing it. Let F be a family of graphs. The Turan number of the family Berge-F is the maximum possible number of edges in an r-uniform hyp ...
ACADEMIC PRESS INC ELSEVIER SCIENCE2019Linearity of saturation for Berge hypergraphs
For a graph F, we say a hypergraph H is a Berge-F if it can be obtained from F by replacing each edge of F with a hyperedge containing it. We say a hypergraph is Berge-F-saturated if it does not contain a Berge-F, but adding any hyperedge creates a copy of ...
ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD2019Saturation of Berge hypergraphs
Given a graph F, a hypergraph is a Berge-F if it can be obtained by expanding each edge in F to a hyperedge containing it. A hypergraph H is Berge-F-saturated if H does not contain a subhypergraph that is a Berge-F, but for any edge e is an element of E((H ...
ELSEVIER SCIENCE BV2019