Results 101 to 110 of about 11,104 (228)
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
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 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
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
Augmenting Naïve Bayes Classifiers with k-Tree Topology
MathematicsThe 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
Regular resolution for CNF of bounded incidence treewidth with few long clauses
, 2019 We demonstrate that Regular Resolution is FPT for two restricted families of CNFs of bounded incidence treewidth. The first includes CNFs having at most $p$ clauses whose removal results in a CNF of primal treewidth at most $k$.
Cali, Andrea, Razgon, Igor
core
Lower Bounds for the Complexity of Monadic Second-Order Logic
, 2010 Courcelle's famous theorem from 1990 states that any property of graphs definable in monadic second-order logic (MSO) can be decided in linear time on any class of graphs of bounded treewidth, or in other words, MSO is fixed-parameter tractable in linear
Kreutzer, Stephan, Tazari, Siamak
core +2 more sources
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
A Solution Merging Heuristic for the Steiner Problem in Graphs Using Tree Decompositions
, 2015 Fixed parameter tractable algorithms for bounded treewidth are known to exist for a wide class of graph optimization problems. While most research in this area has been focused on exact algorithms, it is hard to find decompositions of treewidth ...
CC Ribeiro +4 more
core +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