Results 101 to 110 of about 4,791 (239)
Journal of Graph Theory, Volume 106, Issue 4, Page 816-842, August 2024.Abstract A minimal separator of a graph G is a set S ⊆ V ( G ) such that there exist vertices a , b ∈ V ( G ) ⧹ S with the property that S separates a from b in G, but no proper subset of S does. For an integer k ≥ 0, we say that a minimal separator is k‐simplicial if it can be covered by k cliques and denote by G k the class of all graphs in which ...
Martin Milanič +3 more
wiley +1 more source
Discrete Mathematics, 2006 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Bodlaender, H.L., Koster, A.M.C.A.
openaire +5 more sources
Bidimensional Parameters and Local Treewidth [PDF]
SIAM Journal on Discrete Mathematics, 2004 Summary: For several graph-theoretic parameters such as vertex cover and dominating set, it is known that if their sizes are bounded by \(k\), then the treewidth of the graph is bounded by some function of \(k\). This fact is used as the main tool for the design of several fixed-parameter algorithms on minor-closed graph classes such as planar graphs ...
Demaine, Erik D. +3 more
openaire +2 more sources
Tree independence number I. (Even hole, diamond, pyramid)‐free graphs
Journal of Graph Theory, Volume 106, Issue 4, Page 923-943, August 2024.Abstract The tree‐independence number tree‐ α, first defined and studied by Dallard, Milanič, and Štorgel, is a variant of treewidth tailored to solving the maximum independent set problem. Over a series of papers, Abrishami et al. developed the so‐called central bag method to study induced obstructions to bounded treewidth.
Tara Abrishami +5 more
wiley +1 more source
A more accurate view of the Flat Wall Theorem
Journal of Graph Theory, Volume 107, Issue 2, Page 263-297, October 2024.Abstract We introduce a supporting combinatorial framework for the Flat Wall Theorem. In particular, we suggest two variants of the theorem and we introduce a new, more versatile, concept of wall homogeneity as well as the notion of regularity in flat walls.
Ignasi Sau +2 more
wiley +1 more source
Graphs with at most two moplexes
Journal of Graph Theory, Volume 107, Issue 1, Page 38-69, September 2024.Abstract A moplex is a natural graph structure that arises when lifting Dirac's classical theorem from chordal graphs to general graphs. The notion is known to be closely related to lexicographic searches in graphs as well as to asteroidal triples, and has been applied in several algorithms related to graph classes, such as interval graphs, claw‐free ...
Clément Dallard +4 more
wiley +1 more source
Treewidth of Chordal Bipartite Graphs [PDF]
Journal of Algorithms, 1993 Summary: Chordal bipartite graphs are exactly those bipartite graphs in which every cycle of length at least six has a chord. The treewidth of a graph \(G\) is the smallest maximum cliquesize among all chordal supergraphs of \(G\) decreased by one.
Kloks, A.J.J., Kratsch, D.
openaire +5 more sources
A Strategy for Dynamic Programs: Start over and Muddle through [PDF]
Logical Methods in Computer Science, 2019 In the setting of DynFO, dynamic programs update the stored result of a query whenever the underlying data changes. This update is expressed in terms of first-order logic.
Samir Datta +4 more
doaj +1 more source
On tree decompositions whose trees are minors
Journal of Graph Theory, Volume 106, Issue 2, Page 296-306, June 2024.Abstract In 2019, Dvořák asked whether every connected graph G $G$ has a tree decomposition ( T , B ) $(T,{\rm{ {\mathcal B} }})$ so that T $T$ is a subgraph of G $G$ and the width of ( T , B ) $(T,{\rm{ {\mathcal B} }})$ is bounded by a function of the treewidth of G $G$.
Pablo Blanco +5 more
wiley +1 more source
International Journal of Foundations of Computer Science, 1993 In this paper we show that the treewidth of a circle graph can be computed in polynomial time. A circle graph is a graph that is isomorphic to the intersection graph of a finite collection of chords of a circle. The TREEWIDTH problem can be viewed upon as the problem of finding a chordal embedding of the graph that minimizes the clique number.
openaire +5 more sources