Zobrazeno 1 - 10
of 173
pro vyhledávání: '"SOUZA, UÉVERTON S."'
One way to define the Matching Cut problem is: Given a graph $G$, is there an edge-cut $M$ of $G$ such that $M$ is an independent set in the line graph of $G$? We propose the more general Conflict-Free Cut problem: Together with the graph $G$, we are
Externí odkaz:
http://arxiv.org/abs/2311.01077
Autor:
Casares, Antonio, Pilipczuk, Marcin, Pilipczuk, Michał, Souza, Uéverton S., Thejaswini, K. S.
We give a simple proof that assuming the Exponential Time Hypothesis (ETH), determining the winner of a Rabin game cannot be done in time $2^{o(k \log k)} \cdot n^{O(1)}$, where $k$ is the number of pairs of vertex subsets involved in the winning con
Externí odkaz:
http://arxiv.org/abs/2310.20433
The Independent Cutset problem asks whether there is a set of vertices in a given graph that is both independent and a cutset. Such a problem is $\textsf{NP}$-complete even when the input graph is planar and has maximum degree five. In this paper, we
Externí odkaz:
http://arxiv.org/abs/2307.02107
We show that every graph $G$ of maximum degree $\Delta$ and sufficiently large order has a vertex cutset $S$ of order at most $\Delta$ that induces a subgraph $G[S]$ of maximum degree at most $\Delta-3$. For $\Delta\in \{ 4,5\}$, we refine this resul
Externí odkaz:
http://arxiv.org/abs/2304.10353
Measures of circuit complexity are usually analyzed to ensure the computation of Boolean functions with economy and efficiency. One of these measures is energy complexity, which is related to the number of gates that output true in a circuit for an a
Externí odkaz:
http://arxiv.org/abs/2210.06739
Autor:
Castonguay, Diane, Coelho, Erika M. M., Coelho, Hebert, Nascimento, Julliano R., Souza, Uéverton S.
In Partition Into Complementary Subgraphs (Comp-Sub) we are given a graph $G=(V,E)$, and an edge set property $\Pi$, and asked whether $G$ can be decomposed into two graphs, $H$ and its complement $\overline{H}$, for some graph $H$, in such a way tha
Externí odkaz:
http://arxiv.org/abs/2210.06714
Autor:
Duarte, Gabriel L., Souza, Uéverton S.
In 2021, Duarte, Oliveira, and Souza [MFCS 2021] showed some problems that are FPT when parameterized by the treewidth of the complement graph (called co-treewidth). Since the degeneracy of a graph is at most its treewidth, they also introduced the s
Externí odkaz:
http://arxiv.org/abs/2210.06703
Publikováno v:
The Electronic Journal of Combinatorics, 30(3), 36:1-36:27, 2023; Proceedings: European Conference on Combinatorics, Graph Theory and Applications, EUROCOMB 2023
An oriented graph is a digraph that does not contain a directed cycle of length two. An (oriented) graph $D$ is $H$-free if $D$ does not contain $H$ as an induced sub(di)graph. The Gy\'arf\'as-Sumner conjecture is a widely-open conjecture on simple g
Externí odkaz:
http://arxiv.org/abs/2209.06171
A graph $G$ is well-covered if every minimal vertex cover of $G$ is minimum, and a graph $G$ is well-dominated if every minimal dominating set of $G$ is minimum. Studies on well-covered graphs were initiated in [Plummer, JCT 1970], and well-dominated
Externí odkaz:
http://arxiv.org/abs/2208.08864
Autor:
Souza, Uéverton S.
Sparse-dense partitions was introduced by Feder, Hell, Klein, and Motwani [STOC 1999, SIDMA 2003] as a tool to solve partitioning problems. In this paper, the following result concerning independent sets in graphs having sparse-dense partitions is pr
Externí odkaz:
http://arxiv.org/abs/2208.04408