Zobrazeno 1 - 10
of 488
pro vyhledávání: '"Szwarcfiter, Jayme"'
Autor:
Gomes, Guilherme C. M., Masquio, Bruno P., Pinto, Paulo E. D., Rautenbach, Dieter, Santos, Vinicius F. dos, Szwarcfiter, Jayme L., Werner, Florian
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 suc
Externí odkaz:
http://arxiv.org/abs/2409.04855
Autor:
Bonomo-Braberman, Flavia, Brandwein, Eric, Oliveira, Fabiano S., Sampaio Jr., Moysés S., Sansone, Agustin, Szwarcfiter, Jayme L.
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) thinness, and several variations, for the classes of cographs, crowns
Externí odkaz:
http://arxiv.org/abs/2303.06070
This paper presents an empirical performance analysis of three project scheduling algorithms dealing with maximizing projects' net present value with unrestricted resources. The selected algorithms, being the most recently cited in the literature, ar
Externí odkaz:
http://arxiv.org/abs/2207.03330
Autor:
Forte, Vinicius L. do, Lin, Min Chih, Lucena, Abilio, Maculan, Nelson, Moyano, Veronica A., Szwarcfiter, Jayme L.
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 except pendant vertices and isolated vertices. This class has been co
Externí odkaz:
http://arxiv.org/abs/2204.11785
Autor:
de Luca, Vitor T. F., Mazzoleni, María Pía, Oliveira, Fabiano S., Santos, Tanilson D., Szwarcfiter, Jayme L.
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 class to the well-known class of EPG graphs. A turn of a path at a gri
Externí odkaz:
http://arxiv.org/abs/2203.04250
Autor:
Gomes, Guilherme C. M., Masquio, Bruno P., Pinto, Paulo E. D., Santos, Vinicius F. dos, Szwarcfiter, Jayme L.
A matching $M$ is a $\mathscr{P}$-matching if the subgraph induced by the endpoints of the edges of $M$ satisfies property $\mathscr{P}$. As examples, for appropriate choices of $\mathscr{P}$, the problems Induced Matching, Uniquely Restricted Matchi
Externí odkaz:
http://arxiv.org/abs/2202.04746
Autor:
Gomes, Guilherme C. M., Masquio, Bruno P., Pinto, Paulo E. D., Santos, Vinicius F. dos, Szwarcfiter, Jayme L.
In 2005, Goddard, Hedetniemi, Hedetniemi and Laskar [Generalized subgraph-restricted matchings in graphs, Discrete Mathematics, 293 (2005) 129 - 138] asked the computational complexity of determining the maximum cardinality of a matching whose vertex
Externí odkaz:
http://arxiv.org/abs/2112.09248
Autor:
Gomes, Guilherme C. M., Santos, Vinicius F. dos, da Silva, Murilo V. G., Szwarcfiter, Jayme L.
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 first polynomial time algorithm for this problem, which has become a crit
Externí odkaz:
http://arxiv.org/abs/2007.04468
Autor:
Bonomo-Braberman, Flavia, Oliveira, Fabiano S., Sampaio Jr., Moysés S., Szwarcfiter, Jayme L.
Publikováno v:
Discrete Applied Mathematics 323 (2022), 76-95
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 proposed, in which graphs in general are expressed in terms of $k$ interv
Externí odkaz:
http://arxiv.org/abs/2006.16991
Autor:
Bonomo-Braberman, Flavia, Gonzalez, Carolina L., Oliveira, Fabiano S., Sampaio Jr., Moysés S., Szwarcfiter, Jayme L.
Publikováno v:
Discrete Applied Mathematics 312 (2022), 52-71
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 solved in polynomial time for graphs with bounded thinness, given a suita
Externí odkaz:
http://arxiv.org/abs/2006.16887