English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

In this work, we present an algorithm that solves partitioning problems on P3 convexity for graphs with limited treewidth. Given a graph G = (V,E) and X ⊆ V , we say that X is a p3-convex set if any vertex with at least two neighbors in X is also an element of it. The collection of all p3-convex sets contained in V constitutes the P3 convexity of G. The p-partition problem on P3 convexity consists of partitioning V into p non-empty and pairwise disjoint p3-convex sets, for an integer p ≥ 2. Despite the NP-completeness even for split graphs, we show that such a partitioning problem is solvable in linear time when the treewidth of a graph and p are both limited. Resumo. Neste trabalho, apresentamos um algoritmo que resolve o problema de partição na convexidade P3 quando restrito a grafos com treewidth limitada. Dados um grafoG = (V,E) eX ⊆ V , dizemos queX é um conjunto p3-convexo se todo vértice com pelo menos dois vizinhos em X também pertence a X . A coleção de todos os subconjuntos p3-convexos de V constitui a convexidade P3 em G. O problema da p-partição na convexidade P3 consiste em particionar V em p conjuntos p3-convexos não-vazios e mutualmente disjuntos, para um inteiro p ≥ 2. Apesar da NP-completude mesmo para grafos split, mostramos que o problema é resolvido em tempo linear para grafos com treewidth e o número p limitados.

Particularidades do Problema de Partição na Convexidade P3 em Grafos com Treewidth Limitada