Bruno Porto Masquio

dblp:218/7011 · DBLP profile ↗
← Back
5ranked-venue papers
0as first author
5since 2021 · last 2026
0000-0002-9999-0029ORCID · reported

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 5 · 5 since 2021
YearPublicationVenuePosition
2026 Complexity of deciding the equality of matching numbers
abstract
A matching is said to be disconnected if the saturated vertices induce a disconnected subgraph and induced if the saturated vertices induce a 1-regular graph. The disconnected and induced matching numbers are defined as the maximum cardinality of such matchings, respectively, and are known to be NP-hard to compute. In this paper, we study the relationship between these two parameters and the matching number. In particular, we discuss the complexity of two decision problems; first: deciding if the matching number and disconnected matching number are equal; second: deciding if the disconnected matching number and induced matching number are equal. We show that given a bipartite graph with diameter four, deciding if the matching number and disconnected matching number are equal is NP-complete; the same holds for bipartite graphs with maximum degree three. We characterize diameter three graphs with equal matching number and disconnected matching number, which yields a polynomial time recognition algorithm. Afterwards, we show that deciding if the induced and disconnected matching numbers are equal is co-NP-complete for bipartite graphs of diameter 3. When the induced matching number is large enough compared to the maximum degree, we characterize graphs where these parameters are equal, which results in a polynomial time algorithm for bounded degree graphs.
Guilherme de C. M. Gomes, Bruno Porto Masquio, Paulo E. D. Pinto, Dieter Rautenbach, Vinícius Fernandes dos Santos, Jayme Luiz Szwarcfiter, Florian Werner 0003
J. Comput. Syst. Sci.2
2025 Weighted connected matchings
Guilherme de C. M. Gomes, Bruno Porto Masquio, Paulo E. D. Pinto, Vinícius Fernandes dos Santos, Jayme Luiz Szwarcfiter
Theor. Comput. Sci.2
2023 Disconnected matchings
Guilherme de C. M. Gomes, Bruno Porto Masquio, Paulo E. D. Pinto, Vinícius Fernandes dos Santos, Jayme Luiz Szwarcfiter
Theor. Comput. Sci.2
2022 Weighted Connected Matchings
Guilherme de C. M. Gomes, Bruno Porto Masquio, Paulo E. D. Pinto, Vinícius Fernandes dos Santos, Jayme Luiz Szwarcfiter
LATIN2
2021 Disconnected Matchings
Guilherme de C. M. Gomes, Bruno Porto Masquio, Paulo E. D. Pinto, Vinícius Fernandes dos Santos, Jayme Luiz Szwarcfiter
COCOON2