Pedro P. Medeiros

dblp:330/5488 · DBLP profile ↗
← Back
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
YearPublicationVenuePosition
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
IWOCA3
2023 On the hull and interval numbers of oriented graphs (Brief Announcement)
abstract
In 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
LAGOS3