VLDB 2026 Research / reviewers in the wild / expert
Pedro P. Medeiros
dblp:330/5488
· DBLP profile ↗
2ranked-venue papers
0as first author
2since 2021 · last 2026
—ORCID · none
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 2 · 2 since 2021
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2026 | On the Rank and the General Position Number in Cycle Convexity
Júlio Araújo 0001, Samuel N. Araújo, Pedro P. Medeiros, Nicolas Nisse, Caroline Aparecida de Paula Silva |
IWOCA | 3 |
| 2023 | On the hull and interval numbers of oriented graphs (Brief Announcement)abstractIn this work, for a given oriented graph D, we study its interval and hull numbers, denoted by ⃗in (D) and ⃗hn (D), respectively, in the oriented geodetic, ⃗P3 and ⃗P*3 convexities. This last one, we believe to be formally defined and first studied in this paper, although its undirected version is well-known in the literature. Concerning bounds, for a strongly oriented graph D and the oriented geodetic convexity, we prove that ⃗hn g(D) ≤ m(D)-n(D) + 2 and that there is at least one such that ⃗hn g(D) = m(D) - n(D). We also determine exact values for the hull numbers in these three convexities for tournaments, which imply polynomial-time algorithms to compute them. These results allow us to deduce polynomial-time algorithms to compute ⃗hn P3 (D) when the underlying graph of D is split or cobipartite. Moreover, we provide a meta-theorem by proving that if deciding whether ⃗ing(D) ≤ k or ⃗hn g(D) ≤ k is NP-hard or W[i]-hard parameterized by k, for some i ϵ Z*+, then the same holds even if the underlying graph of D is bipartite. Next, we prove that deciding whether ⃗hn P3 (D) ≤ k or ⃗hn P3* (D) ≤ k is W[2]-hard parameterized by k, even if the underlying graph of D is bipartite; that deciding whether ⃗in P3(D) ≤ k or whether ⃗in P3*(D) ≤ k is NP-complete, and the same for ⃗hn P3*(D) ≤ k even if D has no directed cycles and the underlying graph of D is a chordal bipartite graph; and that deciding whether ⃗in P3(D) ≤ k or whether ⃗in P3*(D) ≤ k is W[2]-hard parameterized by k, even if the underlying graph of D is split. Finally, we also argue that the interval and hull numbers in the ⃗P3 and ⃗P*3 convexities can be computed in polynomial time for directed graphs with underlying graph of bounded tree-width by using Courcelle's theorem. Júlio Araújo 0001, Ana Karolinna Maia, Pedro P. Medeiros, Lucia Draque Penso |
LAGOS | 3 |