Results 91 to 100 of about 1,532 (205)

The product structure of squaregraphs

Journal of Graph Theory, Volume 105, Issue 2, Page 179-191, February 2024.
Abstract A squaregraph is a plane graph in which each internal face is a 4‐cycle and each internal vertex has degree at least 4. This paper proves that every squaregraph is isomorphic to a subgraph of the semistrong product of an outerplanar graph and a path.
Robert Hickingbotham, Paul Jungeblut, Laura Merker, David R. Wood   +3 more
wiley   +1 more source

Augmenting Naïve Bayes Classifiers with k-Tree Topology

Mathematics
The Bayesian network is a directed, acyclic graphical model that can offer a structured description for probabilistic dependencies among random variables.
Fereshteh R. Dastjerdi, Liming Cai
doaj   +1 more source

Robust transshipment problem under consistent flow constraints

Networks, Volume 83, Issue 1, Page 53-82, January 2024.
Abstract In this article, we study robust transshipment under consistent flow constraints. We consider demand uncertainty represented by a finite set of scenarios and characterize a subset of arcs as so‐called fixed arcs. In each scenario, we require an integral flow that satisfies the respective flow balance constraints. In addition, on each fixed arc,
Christina Büsing, Arie M. C. A. Koster, Sabrina Schmitz   +2 more
wiley   +1 more source

Clustered Coloring of Graphs with Bounded Layered Treewidth and Bounded Degree [PDF]

, 2022
Chun‐Hung Liu, David R. Wood
openalex   +1 more source

Girth and treewidth

Journal of Combinatorial Theory, Series B, 2005
Graphs of high girth have been much studied, especially in the context of the minimum vertex number of graphs of given girth and minimum degree. The authors study the treewidth \(\text{tw}(G)\) of a graph \(G\), giving a lower bound in terms of the girth \(g(G)\) and average degree \(d(G)\). They show that \[ \text{tw}(G)\geq c {1\over g(G)+1} (d(G)-1)^
Chandran, L.Sunil, Subramanian, C.R.
openaire   +2 more sources

Approximating the Treewidth of AT-Free Graphs

Discrete Applied Mathematics, 2000
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Bouchitté, Vincent, Todinca, Ioan
openaire   +4 more sources

Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms [PDF]

, 2021
Julien Baste, Ignasi Sau, Dimitrios M. Thilikos   +2 more
openalex   +1 more source

Semantic Tree-Width and Path-Width of Conjunctive Regular Path Queries [PDF]

Logical Methods in Computer Science
We show that the problem of whether a query is equivalent to a query of tree-width $k$ is decidable, for the class of Unions of Conjunctive Regular Path Queries with two-way navigation (UC2RPQs).
Diego Figueira, Rémi Morvan
doaj   +1 more source

Cop-width, flip-width and strong colouring numbers [PDF]

Discrete Mathematics & Theoretical Computer Science
Cop-width and flip-width are new families of graph parameters introduced by Toru\'nczyk (2023) that generalise treewidth, degeneracy, generalised colouring numbers, clique-width and twin-width.
Robert Hickingbotham
doaj   +1 more source

Feedback Vertex Sets in (Directed) Graphs of Bounded Degeneracy or Treewidth [PDF]

, 2022
Kolja Knauer, Hoang La, Petru Valicov
openalex   +1 more source