Results 81 to 90 of about 4,776 (247)
Short note of supertree-width and n-Superhypertree-width [PDF]
Neutrosophic Sets and SystemsThis paper investigates the properties of tree-width and related graph width parameters for n SuperHyperGraphs, a broader generalization of hypergraphs.
Takaaki Fujita
doaj +1 more source
European Journal of Combinatorics, 2012 We prove that for every graph $G$ with $n$ vertices, the treewidth of $G$ plus the treewidth of the complement of $G$ is at least $n-2$. This bound is tight.
Joret, Gwenaël, Wood, D.
openaire +3 more sources
Knot Diagrams of Treewidth Two [PDF]
, 2020 In this paper, we study knot diagrams for which the underlying graph has treewidth two. We give a linear time algorithm for the following problem: given a knot diagram of treewidth two, does it represent the unknot? We also show that for a link diagram of treewidth two we can test in linear time if it represents the unlink.
Bodlaender, Hans L. +3 more
openaire +5 more sources
Tractable Inference for Hybrid Bayesian Networks with NAT-Modeled Dynamic Discretization
Proceedings of the International Florida Artificial Intelligence Research Society Conference, 2022 Hybrid BNs (HBNs) extend Bayesian networks (BNs) to both discrete and continuous variables. Among inference methods for HBNs, we focus on dynamic discretization (DD) that converts HBN to discrete BN for inference.
Yang Xiang, Hanwen Zheng
doaj +1 more source
On Endomorphism Universality of Sparse Graph Classes
Journal of Graph Theory, Volume 110, Issue 2, Page 223-244, October 2025.ABSTRACT We show that every commutative idempotent monoid (a.k.a. lattice) is the endomorphism monoid of a subcubic graph. This solves a problem of Babai and Pultr and the degree bound is best‐possible. On the other hand, we show that no class excluding a minor can have all commutative idempotent monoids among its endomorphism monoids. As a by‐product,
Kolja Knauer, Gil Puig i Surroca
wiley +1 more source
Solving Integer Linear Programs by Exploiting Variable-Constraint Interactions: A Survey
Algorithms, 2019 Integer Linear Programming (ILP) is among the most successful and general paradigms for solving computationally intractable optimization problems in computer science.
Robert Ganian, Sebastian Ordyniak
doaj +1 more source
Intersection Dimension and Graph Invariants
Discussiones Mathematicae Graph Theory, 2021 We show that the intersection dimension of graphs with respect to several hereditary properties can be bounded as a function of the maximum degree. As an interesting special case, we show that the circular dimension of a graph with maximum degree Δ is at
Aravind N.R., Subramanian C.R.
doaj +1 more source
On the k-rainbow domination in graphs with bounded tree-width
Electronic Journal of Graph Theory and Applications, 2021 Given a positive integer k and a graph G = (V, E), a function f from V to the power set of Ik is called a k-rainbow function if for each vertex v ∈ V, f(v)=∅ implies ∪u ∈ N(v)f(u)=Ik where N(v) is the set of all neighbors of vertex v and Ik = {1, …, k ...
M. Alambardar Meybodi +3 more
doaj +1 more source
First-order queries on classes of structures with bounded expansion [PDF]
Logical Methods in Computer Science, 2020 We consider the evaluation of first-order queries over classes of databases with bounded expansion. The notion of bounded expansion is fairly broad and generalizes bounded degree, bounded treewidth and exclusion of at least one minor.
Wojtek Kazana, Luc Segoufin
doaj +1 more source
Tight Distance Query Reconstruction for Trees and Graphs Without Long Induced Cycles
Random Structures &Algorithms, Volume 66, Issue 4, July 2025.ABSTRACT Given access to the vertex set V$$ V $$ of a connected graph G=(V,E)$$ G=\left(V,E\right) $$ and an oracle that given two vertices u,v∈V$$ u,v\in V $$, returns the shortest path distance between u$$ u $$ and v$$ v $$, how many queries are needed to reconstruct E$$ E $$?
Paul Bastide, Carla Groenland
wiley +1 more source