EXAGRAPH: Graph and combinatorial methods for enabling exascale applications
Combinatorial algorithms in general and graph algorithms in particular play a critical
enabling role in numerous scientific applications. However, the irregular memory access …
enabling role in numerous scientific applications. However, the irregular memory access …
Approximation algorithms in combinatorial scientific computing
We survey recent work on approximation algorithms for computing degree-constrained
subgraphs in graphs and their applications in combinatorial scientific computing. The …
subgraphs in graphs and their applications in combinatorial scientific computing. The …
On the manipulability of maximum vertex-weighted bipartite b-matching mechanisms
G Auricchio, J Zhang - ECAI 2023, 2023 - ebooks.iospress.nl
In this paper, we study the Maximum Vertex-weighted b-Matching (MVbM) problem on
bipartite graphs in a new game-theoretical environment. In contrast to other game …
bipartite graphs in a new game-theoretical environment. In contrast to other game …
A 2/3-approximation algorithm for vertex-weighted matching
We consider the maximum vertex-weighted matching problem (MVM) for non-bipartite
graphs in which non-negative weights are assigned to the vertices of a graph and a …
graphs in which non-negative weights are assigned to the vertices of a graph and a …
New approximation algorithms for minimum weighted edge cover
Abstract We describe two new 3/2-approximation algorithms and a new 2-approximation
algorithm for the minimum weight edge cover problem in graphs. We show that one of the …
algorithm for the minimum weight edge cover problem in graphs. We show that one of the …
Edge Manipulations for the Maximum Vertex-Weighted Bipartite -matching
G Auricchio, J Liu, Q Ma, J Zhang - ACM Transactions on Intelligent …, 2023 - dl.acm.org
In this paper, we explore the Mechanism Design aspects of the Maximum Vertex-weighted-
Matching (MVbM) problem on bipartite graphs. The set comprises agents, while represents …
Matching (MVbM) problem on bipartite graphs. The set comprises agents, while represents …
Strong bounds and exact solutions to the minimum broadcast time problem
M Ivanova, D Haugland… - … Transactions in Operational …, 2025 - Wiley Online Library
Given a graph and a subset of its nodes, referred to as source nodes, the minimum
broadcast time problem asks for the minimum number of steps in which a signal can be …
broadcast time problem asks for the minimum number of steps in which a signal can be …
A Parallel 2/3-Approximation Algorithm for Vertex-Weighted Matching∗
We consider the maximum vertex-weighted matching problem (MVM), in which non-negative
weights are assigned to the vertices of a graph, and the weight of a matching is the sum of …
weights are assigned to the vertices of a graph, and the weight of a matching is the sum of …
[PDF][PDF] Computing the broadcast time of a graph
M Ivanova, D Haugland, BH Tvedt - arXiv preprint arXiv:2107.06359, 2021 - academia.edu
Given a graph and a subset of its nodes, referred to as source nodes, the minimum
broadcast problem asks for the minimum number of steps in which a signal can be …
broadcast problem asks for the minimum number of steps in which a signal can be …
Approximation Algorithms for Maximum Vertex-Weighted Matching
A Al-Herz - 2019 - search.proquest.com
We consider the maximum vertex-weighted matching problem (MVM), in which non-negative
weights are assigned to the vertices of a graph, and the weight of a matching is the sum of …
weights are assigned to the vertices of a graph, and the weight of a matching is the sum of …