Results 81 to 90 of about 306 (178)
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
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
Structural properties of graph products
Journal of Graph Theory, Volume 109, Issue 2, Page 107-136, June 2025.Abstract Dujmovć, Joret, Micek, Morin, Ueckerdt, and Wood established that every planar graph is a subgraph of the strong product of a graph with bounded treewidth and a path. Motivated by this result, this paper systematically studies various structural properties of cartesian, direct and strong products.
Robert Hickingbotham, David R. Wood
wiley +1 more source
On the treewidth of toroidal grids
Discrete Applied Mathematics, 2016 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Masashi Kiyomi +2 more
openaire +2 more sources
On Constrained Minimum Weight Edge Covers With Applications to Emergency Planning
Networks, Volume 85, Issue 3, Page 261-271, April 2025.ABSTRACT In this paper we present a new covering problem, called Min Cost q$$ q $$‐Single Location Cover, where we are given a fixed positive integer q$$ q $$, a finite ground set J$$ J $$, an integral positive demand dj$$ {d}_j $$ for each element j∈J$$ j\in J $$, a collection 𝒥 of subsets of J$$ J $$, an integral positive cost cS$$ {c}_S $$ and an ...
Shai Dimant, Sven O. Krumke
wiley +1 more source
Phylogenetic incongruence through the lens of Monadic Second Order logic
Journal of Graph Algorithms and Applications, 2016 Within the field of phylogenetics there is growing interest in measures for summarising the dissimilarity, or incongruence, of two or more phylogenetic trees. Many of these measures are NP-hard to compute and this has stimulated a considerable volume of
Steven Kelk +3 more
doaj +1 more source
On Treewidth and Stable Marriage
CoRR, 2017 Stable Marriage is a fundamental problem to both computer science and economics. Four well-known NP-hard optimization versions of this problem are the Sex-Equal Stable Marriage (SESM), Balanced Stable Marriage (BSM), max-Stable Marriage with Ties (max-SMT) and min-Stable Marriage with Ties (min-SMT) problems.
Sushmita Gupta +2 more
openaire +2 more sources
Optimal Padded Decomposition For Bounded Treewidth Graphs [PDF]
TheoretiCSA $(β,δ,Δ)$-padded decomposition of an edge-weighted graph $G = (V,E,w)$ is a stochastic decomposition into clusters of diameter at most $Δ$ such that for every vertex $v\in V$, the probability that $\rm{ball}_G(v,γΔ)$ is entirely contained in the ...
Arnold Filtser +6 more
doaj +1 more source
On the tree-width of knot diagrams
Journal of Computational Geometry, 2019 We show that a small tree-decomposition of a knot diagram induces a small sphere-decomposition of the corresponding knot. This, in turn, implies that the knot admits a small essential planar meridional surface or a small bridge sphere.
Saul Schleimer +3 more
doaj +1 more source
Heuristic computation of exact treewidth
CoRR, 2022 We are interested in computing the treewidth $\tw(G)$ of a given graph $G$. Our approach is to design heuristic algorithms for computing a sequence of improving upper bounds and a sequence of improving lower bounds, which would hopefully converge to $\tw(G)$ from both sides.
openaire +4 more sources