L. L. Pedrosa

activity

20112026

collaborators

Showing 2019Show all

2 papers · 1 filter

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 2-approximation for the k-prize-collecting Steiner tree problem

Computing the largest bond of a graph

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