48 artigos
Este artigo apresenta uma prova curta e autossuficiente do teorema de Delahan, demonstrando que todo grafo simples com vértices ocorre como um subgrafo induzido em um grafo de Steinhaus com vértices, utilizando o conceito de conjuntos de índices geradores para triângulos de Steinhaus.
Este artigo caracteriza a solvabilidade de um novo tipo de quebra-cabeça de ordenação em grades, fornecendo uma fórmula para contar soluções válidas, um algoritmo linear para corrigir configurações insolúveis e demonstrando que a generalização do problema para permutações arbitrárias é NP-completa.
Este artigo investiga a propriedade WELLDOC em palavras infinitas, estabelecendo um critério para sua ocorrência em palavras geradas por morfismos.
Este artigo apresenta uma caracterização completa dos digrafos de ninho intervalar por meio de ordenações lineares de vértices com padrões proibidos, denominadas "nest orderings", completando assim o quadro de caracterizações por ordenação de vértices entre as principais subclasses de digrafos intervalares.
Este artigo apresenta uma descrição completa e otimizada de um algoritmo que estima o grau médio de grafos com arboricidade limitada, eliminando fatores logarítmicos desnecessários e alcançando uma complexidade de consulta de .
Este artigo apresenta uma versão do teorema da árvore matricial que relaciona o determinante de uma matriz a somas de pesos de arborescências em grafos direcionados, permitindo somas de colunas não nulas através da adição de um vértice raiz, e aplica esses resultados para provar um teorema de florestas matriciais e calcular a evolução temporal de sistemas com estados discretos.
Este artigo desenvolve ferramentas para o estudo quantitativo das árvores geradoras mínimas aleatórias (MST), abordando tanto o caso padrão de pesos independentes e identicamente distribuídos quanto generalizações para medidas produto com distribuições arbitrárias.
Este artigo investiga as propriedades do número cromático linear, um parâmetro relaxado da profundidade de árvore introduzido por Kun et al., e estabelece limites aprimorados para essa relação em várias classes de grafos.
Este artigo fornece a justificativa teórica para o framework -DRESS, provando incondicionalmente que ele distingue pares CFI específicos e demonstrando condicionalmente que sua capacidade de distinção é pelo menos equivalente à hierarquia -WL para todos os grafos.
Este artigo estabelece limites de fase para a probabilidade de um conjunto aleatório de subconjuntos definir uma base de matroide, demonstra que tais estruturas são quase certamente matroides pavimentados esparsos quando a condição é satisfeita, e utiliza um algoritmo guloso para refinar as estimativas assintóticas do número de matroides, pavimentados e esparsos pavimentados, permitindo que o posto cresça lentamente com .
Este artigo determina a estrutura completa dos valores nim para jogos de subtração aditiva no regime quadrático primitivo, fornecendo uma prova definitiva para uma fórmula fechada clássica envolvendo expressões de Brakets do tipo Beatty que caracteriza as posições P e demonstrando que cada sequência de valores nim reside em um deslocamento linear dessas posições.
Este artigo desenvolve fórmulas explícitas e compactas para o polinômio M de diversos produtos de grafos (como cartesiano, direto, forte, lexicográfico, diferença simétrica, disjunção e produto de Sierpiński), oferecendo uma descrição unificada de como as interações de graus dos vértices se propagam nessas construções e estendendo resultados existentes para índices topológicos baseados em graus.
Este artigo propõe dois métodos quantitativos baseados em valores de referência para calcular vetores de peso a partir de matrizes de comparações pareadas incompletas, estendendo as heurísticas aritmética e geométrica, provando a otimalidade e a existência de solução para a versão geométrica e fornecendo condições suficientes para a versão aritmética.
Os autores apresentam um algoritmo FPT que estende o teorema de Gallai-Milgram, decidindo em tempo polinomial se um grafo pode ser coberto por menos caminhos do que o número de independência, e fornecendo um certificado de independência caso contrário, além de resolver o problema de Hamiltonicidade para grafos com número de independência limitado.
O artigo introduz as sobrepartições separadas por blocos, uma família restrita que interpola entre as partições clássicas e as sobrepartições livres, demonstrando que suas estruturas de contagem são governadas por números de Fibonacci e apresentando suas propriedades analíticas, como expansões em funções simétricas, recorrências e crescimento assintótico.
Os autores provam uma versão enfraquecida da conjectura de Chudnovsky et al., demonstrando que grafos que excluem e a grade como menores induzidos admitem uma decomposição em árvore cujos sacos possuem números de independência de distância controlados por funções polilogarítmicas.
Este artigo apresenta uma generalização abrangente da operação de troca para (n,m)-grafos, estabelecindo resultados fundamentais sobre homomorfismos, resolvendo problemas em aberto de Klostermeyer, MacGillivray e Brewster, definindo um produto categórico e explorando o número cromático associado, inclusive para florestas.
Este artigo investiga a complexidade computacional do problema de reconfiguração de conjuntos dominantes de distância- sob as regras de deslizamento e salto de tokens, estabelecendo uma dicotomia de complexidade ao demonstrar que o problema é tratável em tempo polinomial para grafos divididos quando , enquanto permanece PSPACE-completo para outras classes de grafos como planares, bipartidos e cordais.
Este artigo investiga a complexidade parametrizada do problema do caminho mais curto com restrições disjuntivas positivas, estabelecendo resultados de kernelização e tratabilidade parametrizada fixa para diferentes parâmetros, como o tamanho da solução e propriedades estruturais do grafo de forçamento.
Este artigo investiga a viabilidade de algoritmos quânticos para sistemas lineares na resolução de equações de Poisson tridimensionais heterogêneas aplicadas ao fluxo em fraturas geológicas, demonstrando que, embora o método ofereça vantagens em tempo de execução e economia de memória em relação aos métodos clássicos, a aplicação independente de pré-condicionadores não melhora o número de condição efetivo, permanecendo como uma barreira significativa para a vantagem quântica prática.