Source author record

Marcos C. Vargas

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Data Structures and Algorithms Discrete Mathematics math.OC

Catalog footprint

Research overview

2works

4topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Computing sandpile configurations using integer linear programming

It is well known that recurrent sandpile configurations can be characterized as the optimal solution of certain optimization problems. In this article, we present two new integer linear programming models, one that computes recurrent configurations and other that computes the order of the configuration. Finally, by using duality of linear programming, we are able to compute the identity configuration for the cone of a regular graph.

preprint2014arXiv

Optimum matchings in weighted bipartite graphs

Given an integer weighted bipartite graph $\{G=(U\sqcup V, E), w:E\rightarrow \mathbb{Z}\}$ we consider the problems of finding all the edges that occur in some minimum weight matching of maximum cardinality and enumerating all the minimum weight perfect matchings. Moreover, we construct a subgraph $G_{cs}$ of $G$ which depends on an $ε$ -optimal solution of the dual linear program associated to the assignment problem on $\{G,w\}$ that allows us to reduced this problems to their unweighed variants on $G_{cs}$ . For instance, when $G$ has a perfect matching and we have an $ε$ -optimal solution of the dual linear program associated to the assignment problem on $\{G,w\}$ , we solve the problem of finding all the edges that occur in some minimum weight perfect matching in linear time on the number of edges. Therefore, starting from scratch we get an algorithm that solves this problem in time $O(\sqrt{n}m\log(nW))$ , where $n=|U|\geq |V|$ , $m=|E|$ , and $W={\rm max}\{|w(e)|\, :\, e\in E\}$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.