47 artigos
O artigo apresenta o HYGENE, o primeiro método baseado em difusão e aprendizado profundo para gerar hipergrafos realistas e diversos através de uma abordagem de expansão local progressiva sobre sua representação bipartida.
Este artigo investiga a rigidez de poliedros sob restrições de comprimento de arestas e coplanaridade, demonstrando que, embora existam exemplos flexíveis como o cubo regular, os poliedros convexos são genericamente rígidos em dimensão três.
Este artigo apresenta uma versão mais acessível e simplificada da prova de Ralph Seifert de 1971, demonstrando que não existem digrafos funcionais primos, utilizando a terminologia e o contexto das pesquisas recentes.
O artigo demonstra que um método exato simples resolve a maioria das instâncias clássicas de benchmark do Problema do Caixeiro Viajante com Janelas de Tempo em menos de dez segundos, concluindo que essas instâncias não são mais representativas para avaliação de desempenho e exigem cautela no desenho de conjuntos de treinamento para algoritmos de aprendizado de máquina.
Este artigo apresenta a prova da Conjectura de Erdős sobre Emparelhamento, um problema aberto de longa data na combinatória extrema, que determina o limite superior máximo para o tamanho de uma família de subconjuntos de tamanho que não contém subconjuntos mutuamente disjuntos.
O artigo demonstra que assintoticamente quase todas as funções vetoriais sobre corpos finitos possuem estabilizadores de afinidade estendida triviais, o que implica que o número de classes de equivalência EA é aproximadamente igual à estimativa ingênua e que a probabilidade de duas funções amostradas independentemente serem equivalentes é superexponencialmente pequena.
Este trabalho apresenta uma abordagem algorítmica baseada em geração de colunas para resolver o problema de fluxo multicommodity com função objetivo convexa, oferecendo métodos eficientes para as variantes fracionária e não fracionária que minimizam custos de enlace crescentes conforme a utilização, com aplicações críticas em redes de telecomunicações.
Este artigo determina sistematicamente o índice cromático circular de pequenos grafos e multigrafos com grau máximo até 6, construindo famílias infinitas de exemplos que refutam variantes da "Conjectura do Lacuna Superior" sobre a não existência de grafos com índice cromático circular logo abaixo de .
Este artigo investiga o polinômio de dominação do grafo co-maximal do anel de inteiros módulo , derivando fórmulas explícitas para casos específicos que demonstram unimodalidade e log-cavidade, estabelecendo expressões estruturais para geral e analisando as raízes de dominação e seus limites de módulo.
Este artigo investiga uma família de instâncias de Max-Cut com pesos de arestas geométricos, estabelecendo um diagrama de fases preciso para cortes isolados com base em polinômios de limiar e conjecturando que esses cortes são globalmente ótimos para .
Este artigo apresenta o espectro de adjacência ponderada de grafos multipartidos completos e grafos coroa, caracteriza famílias com três autovalores distintos, identifica matrizes integrais, corrige resultados anteriores sobre a diminuição da energia e do raio espectral após a remoção de arestas, e resolve um problema aberto relacionado à energia ISI em grafos multipartidos.
Este artigo identifica três condições necessárias para a existência de uma orientação acíclica com paridade de grau de entrada restrita, define classes polinomiais onde essas condições são suficientes, estabelece suas relações de inclusão e caracteriza os casos solúveis em produtos cartesianos de caminhos e ciclos, oferecendo algoritmos construtivos para encontrar tais orientações em tempo polinomial.
Este artigo generaliza resultados anteriores sobre suportes para hipergrafos definidos por regiões não penetrantes, demonstrando que, para um grafo hospedeiro de gênero limitado e subgrafos "livres de cruzamento", é possível construir um suporte também de gênero limitado, o que unifica a análise de problemas de empacotamento e cobertura e permite aplicações em coloração de hipergrafos.
Este artigo investiga a densidade de arestas em desenhos de grafos que evitam um tipo específico de célula, estabelecendo limites superiores e inferiores para diversas combinações de estilos de desenho e tipos de grafos, caracterizando quais grafos simples admitem tais desenhos e melhorando o limite inferior conhecido para desenhos quase-planos não homotópicos.
Este artigo emprega o framework de localização para aprimorar os limites superiores existentes em problemas de teoria extremal de grafos e fornecer caracterizações estruturais dos grafos extremos que atingem esses limites.
Este artigo demonstra que, para conjuntos de árvores filogenéticas com pouca estrutura comum, o número de reticulações necessárias para exibi-las em uma rede permanece próximo do limite trivial, aproximando-se do limite superior conhecido para exibir todas as árvores possíveis.
Este artigo constrói autômatos para reconhecer relações em sequências -automáticas, estabelece uma relação entre a complexidade de subpalavras e a complexidade de estados de subsequências lineares, resolve uma questão recente sobre o formato de entrada mais significativo primeiro e analisa a complexidade computacional de tais construções usando aritmética de Büchi.
Este artigo estabelece uma prova completa para a validade do limite superior para o número de dominação dupla em grafos outerplanares maximais, corrigindo uma demonstração anterior considerada incompleta.
Este artigo fornece fórmulas explícitas para polinômios de posição geral em grafos multipartidos completos, demonstrando que a unimodalidade e a log-concavidade se mantêm para tamanhos de partição até quatro, mas falham para tamanhos maiores, além de provar que a unimodalidade é preservada em coronas de diversas classes naturais de grafos.
O artigo demonstra que a diferença entre o tamanho mínimo de um circuito booleano e o de uma fórmula sobre a base AIG é sempre 0 ou 1, estabelecendo teoremas que definem quando o compartilhamento de portas é necessário e como essa lacuna unitária surge exclusivamente de um único gate com fan-out 2.