L. L. Pedrosa

activity

20192022

collaborators

4 papers

cs.DS2022

A parameterized approximation algorithm for the Multiple Allocation $k$ -Hub Center

Marcelo P. L. Benedito, Lucas P. Melo, Lehilton L. C. Pedrosa

In the Multiple Allocation $k$ -Hub Center (MA $k$ HC), we are given a connected edge-weighted graph $G$ , sets of clients $C$ and hub locations $H$ , where ${V(G) =…

cs.DS2020

Computing the Largest Bond and the Maximum Connected Cut of a Graph

Gabriel L. Duarte, Hiroshi Eto, Tesshu Hanaka +6

The cut-set $\partial (S)$ of a graph $G = (V, E)$ is the set of edges that have one endpoint in $S \subset V$ and the other endpoint in $V ∖ S$ , and whenever $G [S]$ is connected…

cs.CC2019

A 2-approximation for the $k$ -prize-collecting Steiner tree problem

Lehilton Lelis Chaves Pedrosa, Hugo Kooki Kasuya Rosado

We consider the $k$ -prize-collecting Steiner tree problem. An instance is composed of an integer $k$ and a graph $G$ with costs on edges and penalties on vertices. The objective is…

cs.DS2019

Computing the largest bond of a graph

Gabriel L. Duarte, Daniel Lokshtanov, Lehilton L. C. Pedrosa +2

A bond of a graph $G$ is an inclusion-wise minimal disconnecting set of $G$ , i.e., bonds are cut-sets that determine cuts $[S, V ∖ S]$ of $G$ such that $G [S]$ and $G[V\setmin…

A parameterized approximation algorithm for the Multiple Allocation k-Hub Center

Computing the Largest Bond and the Maximum Connected Cut of a Graph

A 2-approximation for the k-prize-collecting Steiner tree problem

Computing the largest bond of a graph

A parameterized approximation algorithm for the Multiple Allocation $k$ -Hub Center

A 2-approximation for the $k$ -prize-collecting Steiner tree problem