4 citations · 6 across the 10 of their papers we have counts for
Showing 2017 · cs.DMShow all
3 papers · 2 filters
cs.DM2017
On the Computational Complexity of the Bipartizing Matching Problem
Carlos V. G. C. Lima, Dieter Rautenbach, Uéverton S. Souza +1
We study the problem of determining whether a given graph~ admits a matching~ whose removal destroys all odd cycles of~ (or equivalently whether~ is bipartite).…
cs.DM2017★ 4 cited
Decycling a graph by the removal of a matching: new algorithmic and structural aspects in some classes of graphs
Fábio Protti, Uéverton S. Souza
A graph is {\em matching-decyclable} if it has a matching such that is acyclic. Deciding whether is matching-decyclable is an NP-complete problem even if is 2…
cs.DM2017
A general framework for path convexities
João Vinicius C. Thompson, Loana T. Nogueira, Fábio Protti +3
In this work we deal with the so-called path convexities, defined over special collections of paths. For example, the collection of the shortest paths in a graph is associated with…