37 citations · 115 across the 24 of their papers we have counts for
28 papers
Complexity of Deciding the Equality of Matching Numbers
Guilherme C. M. Gomes, Bruno P. Masquio, Paulo E. D. Pinto +4
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…
Thinness and its variations on some graph families and coloring graphs of bounded thinness
Flavia Bonomo-Braberman, Eric Brandwein, Fabiano S. Oliveira +3
Interval graphs and proper interval graphs are well known graph classes, for which several generalizations have been proposed in the literature. In this work, we study the (proper)…
Empirical Evaluation of Project Scheduling Algorithms for Maximization of the Net Present Value
Isac M. Lacerda, Eber A. Schmitz, Jayme L. Szwarcfiter +1
This paper presents an empirical performance analysis of three project scheduling algorithms dealing with maximizing projects' net present value with unrestricted resources. The se…
Graphs whose vertices of degree at least 2 lie in a triangle
Vinicius L. do Forte, Min Chih Lin, Abilio Lucena +3
A pendant vertex is one of degree one and an isolated vertex has degree zero. A neighborhood star-free (NSF for short) graph is one in which every vertex is contained in a triangle…
Edge Intersection Graphs of Paths on a Triangular Grid
Vitor T. F. de Luca, María Pía Mazzoleni, Fabiano S. Oliveira +2
We introduce a new class of intersection graphs, the edge intersection graphs of paths on a triangular grid, called EPGt graphs. We show similarities and differences from this new…
Weighted Connected Matchings
Guilherme C. M. Gomes, Bruno P. Masquio, Paulo E. D. Pinto +2
A matching is a -matching if the subgraph induced by the endpoints of the edges of satisfies property . As examples, for appropriate choices of $\…
Disconnected Matchings
Guilherme C. M. Gomes, Bruno P. Masquio, Paulo E. D. Pinto +2
In 2005, Goddard, Hedetniemi, Hedetniemi and Laskar [Generalized subgraph-restricted matchings in graphs, Discrete Mathematics, 293 (2005) 129 - 138] asked the computational comple…
Minimum Number of Bends of Paths of Trees in a Grid Embedding
V. T. F. Luca, F. S. Oliveira, J. L. Szwarcfiter
We are interested in embedding trees T with maximum degree at most four in a rectangular grid, such that the vertices of T correspond to grid points, while edges of T correspond to…
B1-EPG representations using block-cutpoint trees
V. T. F. Luca, F. S. Oliveira, J. L. Szwarcfiter
In this paper, we are interested in the edge intersection graphs of paths of a grid where each path has at most one bend, called B1-EPG graphs and first introduced by Golumbic et a…
FPT and kernelization algorithms for the k-in-a-tree problem
Guilherme C. M. Gomes, Vinicius F. dos Santos, Murilo V. G. da Silva +1
The three-in-a-tree problem asks for an induced tree of the input graph containing three mandatory vertices. In 2006, Chudnovsky and Seymour [Combinatorica, 2010] presented the fir…
Precedence thinness in graphs
Flavia Bonomo-Braberman, Fabiano S. Oliveira, Moysés S. Sampaio +1
Interval and proper interval graphs are very well-known graph classes, for which there is a wide literature. As a consequence, some generalizations of interval graphs have been pro…
Thinness of product graphs
Flavia Bonomo-Braberman, Carolina L. Gonzalez, Fabiano S. Oliveira +2
The thinness of a graph is a width parameter that generalizes some properties of interval graphs, which are exactly the graphs of thinness one. Many NP-complete problems can be sol…
Linear-time Algorithms for Eliminating Claws in Graphs
Flavia Bonomo-Braberman, Julliano R. Nascimento, Fabiano S. Oliveira +2
Since many NP-complete graph problems have been shown polynomial-time solvable when restricted to claw-free graphs, we study the problem of determining the distance of a given grap…
The Complexity of Helly- EPG Graph Recognition
Claudson F. Bornstein, Martin Charles Golumbic, Tanilson D. Santos +2
Golumbic, Lipshteyn, and Stern defined in 2009 the class of EPG graphs, the intersection graph class of edge paths on a grid. An EPG graph is a graph that admits a representati…
On the Geodetic Hull Number of Complementary Prisms
Erika M. M. Coelho, Hebert Coelho, Julliano R. Nascimento +1
Let be a finite, simple, and undirected graph and let be a set of vertices of . In the geodetic convexity, a set of vertices of a graph is convex if all vertices…
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).…
Perfect Edge Domination: Hard and Solvable Cases
Min Chih Lin, Vadim Lozin, Veronica A. Moyano +1
Let be an undirected graph. An edge of dominates itself and all edges adjacent to it. A subset of edges of is an edge dominating set of , if every edge of the g…
Constant Threshold Intersection Graphs of Orthodox Paths in Trees
Claudson Ferreira Bornstein, José Wilson Coura Pinto, Dieter Rautenbach +1
A graph belongs to the class for integers , , and if there is a pair , where is a tree of maximum degree at most , and ${\cal…
Distance geometry approach for special graph coloring problems
Rosiane de Freitas, Bruno Dias, Nelson Maculan +1
One of the most important combinatorial optimization problems is graph coloring. There are several variations of this problem involving additional constraints either on vertices or…
Forbidden Induced Subgraphs for Bounded -Intersection Number
Claudson F. Bornstein, Jose W. C. Pinto, Dieter Rautenbach +1
A graph has -intersection number at most if it is possible to assign to every vertex of , a subset of some ground set with in such a way that d…
Parameterized mixed cluster editing via modular decomposition
Maise Dantas da Silva, Fábio Protti, Jayme Luiz Szwarcfiter
In this paper we introduce a natural generalization of the well-known problems Cluster Editing and Bicluster Editing, whose parameterized versions have been intensively investigate…
Efficient and Perfect domination on circular-arc graphs
Min Chih Lin, Michel J. Mizrahi, Jayme L. Szwarcfiter
Given a graph , a \emph{perfect dominating set} is a subset of vertices such that each vertex is dominated by exactly one ve…
An time algorithm for minimum weighted dominating induced matching
Min Chih Lin, Michel J. Mizrahi, Jayme L. Szwarcfiter
Say that an edge of a graph dominates itself and every other edge adjacent to it. An edge dominating set of a graph is a subset of edges which domina…
Towards a provably resilient scheme for graph-based watermarking
Lucila M. S. Bento, Davidson Boccardo, Raphael C. S. Machado +2
Digital watermarks have been considered a promising way to fight software piracy. Graph-based watermarking schemes encode authorship/ownership data as control-flow graph of dummy c…