This paper was published through Galoá and has a deposited DOI. To cite this paper, use one of the standards below:
In case you are one of the co-authors and want to register this paper in your Lattes, use the following code: doi > 10.59254/sbpo-2020-122605
If you've NEVER registered a DOI in your Lattes, check our tutorial!Partitioning split graphs into two trees
Uéverton Souza
Universidade Federal Fluminense
Now you could share with me your questions, observations and congratulations
Create a topicSeja G = (V,E) um grafo simples e não direcionado. Neste trabalho, consideramos o problema de particionar V (G) = A∪B, A∩B = ∅, tal que cada A e B induzem uma árvore (i.e, um subgrafo acíclico e conexo). Os grafos que admitem essa partição foram denominados grafos de Yutsis e seus estudos estão relacionados aos estudos de grafos planares Hamiltonianos. O reconhecimento de grafos de Yutsis é NP-completo para grafos gerais e, até o momento, não há estudos considerando a caracterização de grafos de Yutsis para classes de grafos específicas. Este trabalho se restringe a reconhecer grafos split (grafos cujo conjunto de vértices pode ser particionado em um conjunto independente e num clique) que são de Yutsis. Mais especificamente, fornecemos uma caracterização por subgrafos proibidos que conduz a um algoritmo polinomial de reconhecimento dos grafos split que são Yutsis.
With nearly 200,000 papers published, Galoá empowers scholars to share and discover cutting-edge research through our streamlined and accessible academic publishing platform.
Learn more about our products:
This proceedings is identified by a DOI , for use in citations or bibliographic references. Attention: this is not a DOI for the paper and as such cannot be used in Lattes to identify a particular work.
Check the link "How to cite" in the paper's page, to see how to properly cite the paper