Zobrazeno 1 - 10
of 1 642
pro vyhledávání: '"LIMA, A. T."'
Autor:
Lima, Paloma T., Nikabadi, Amir
A family $\mathcal{F}$ of graphs is a \textit{Gallai family} if for every connected graph $G\in \mathcal{F}$, all longest paths in $G$ have a common vertex. While it is not known whether $P_5$-free graphs are a Gallai family, Long Jr., Milans, and Mu
Externí odkaz:
http://arxiv.org/abs/2409.07366
Autor:
Lima, Paloma T., Milanič, Martin, Muršič, Peter, Okrasa, Karolina, Rzążewski, Paweł, Štorgel, Kenny
For a tree decomposition $\mathcal{T}$ of a graph $G$, by $\mu(\mathcal{T})$ we denote the size of a largest induced matching in $G$ all of whose edges intersect one bag of $\mathcal{T}$. Induced matching treewidth of a graph $G$ is the minimum value
Externí odkaz:
http://arxiv.org/abs/2402.15834
Autor:
Agrawal, Akanksha, Lima, Paloma T., Lokshtanov, Daniel, Rzążewski, Pawel, Saurabh, Saket, Sharma, Roohani
An independent set in a graph G is a set of pairwise non-adjacent vertices. A graph $G$ is bipartite if its vertex set can be partitioned into two independent sets. In the Odd Cycle Transversal problem, the input is a graph $G$ along with a weight fu
Externí odkaz:
http://arxiv.org/abs/2402.11465
Autor:
Magliano, Christian, Kostov, Veselin, Cacciapuoti, Luca, Covone, Giovanni, Inno, Laura, Fiscale, Stefano, Kuchner, Marc, Quintana, Elisa V., Salik, Ryan, Saggese, Vito, Yablonsky, John M., Fornear, Aline U., Hyogo, Michiharu, Di Fraia, Marco Z., Luca, Hugo A. Durantini, de Lambilly, Julien S., Oliva, Fabrizio, Pagano, Isabella, Ienco, Riccardo M., de Lima, Lucas T., Andrés-Carcasona, Marc, Gallo, Francesco, Acharya, Sovan
The Transiting Exoplanet Survey Satellite (TESS) mission is providing the scientific community with millions of light curves of stars spread across the whole sky. Since 2018 the telescope has detected thousands of planet candidates that need to be me
Externí odkaz:
http://arxiv.org/abs/2303.00624
Autor:
Bodlaender, Hans L., Bonnet, Édouard, Jaffke, Lars, Knop, Dušan, Lima, Paloma T., Milanič, Martin, Ordyniak, Sebastian, Pandey, Sukanya, Suchý, Ondřej
In this paper, we give a very simple proof that Treewidth is NP-complete; this proof also shows NP-completeness on the class of co-bipartite graphs. We then improve the result by Bodlaender and Thilikos from 1997 that Treewidth is NP-complete on grap
Externí odkaz:
http://arxiv.org/abs/2301.10031
Autor:
Lima, Joana T.1,2,3 (AUTHOR), Ferreira, Jorge G.1,2 (AUTHOR) jferreir@ibmc.up.pt
Publikováno v:
Nucleus (1949-1034). Dec2024, Vol. 15 Issue 1, p1-16. 16p.
We show that the $b$-Coloring problem is complete for the class XNLP when parameterized by the pathwidth of the input graph. Besides determining the precise parameterized complexity of this problem, this implies that b-Coloring parameterized by pathw
Externí odkaz:
http://arxiv.org/abs/2209.07772
Publikováno v:
Proceedings: ACM-SIAM Symposium on Discrete Algorithms, SODA 2023
We study a generalization of the classic Global Min-Cut problem, called Global Label Min-Cut (or sometimes Global Hedge Min-Cut): the edges of the input (multi)graph are labeled (or partitioned into color classes or hedges), and removing all edges of
Externí odkaz:
http://arxiv.org/abs/2207.07426
Autor:
Hatzel, Meike, Jaffke, Lars, Lima, Paloma T., Masařík, Tomáš, Pilipczuk, Marcin, Sharma, Roohani, Sorge, Manuel
Publikováno v:
Proceedings: ACM-SIAM Symposium on Discrete Algorithms, SODA 2023
We show fixed-parameter tractability of the Directed Multicut problem with three terminal pairs (with a randomized algorithm). This problem, given a directed graph $G$, pairs of vertices (called terminals) $(s_1,t_1)$, $(s_2,t_2)$, and $(s_3,t_3)$, a
Externí odkaz:
http://arxiv.org/abs/2207.07425
Autor:
Jaffke, Lars, Lima, Paloma T.
We determine the maximum number of edges that a planar graph can have as a function of its maximum degree and matching number.
Externí odkaz:
http://arxiv.org/abs/2207.03130