Results 31 to 40 of about 28,286 (155)
A superclass of Edge-Path-Tree graphs with few cliques [PDF]
Operations Research Letters, 2009 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
CARAMIA, MASSIMILIANO, Apollonio, N.
openaire +5 more sources
Log-space Algorithms for Paths and Matchings in k-trees [PDF]
, 2010 Reachability and shortest path problems are NL-complete for general graphs. They are known to be in L for graphs of tree-width 2 [JT07]. However, for graphs of tree-width larger than 2, no bound better than NL is known.
Das, Bireswar +2 more
core +3 more sources
BMC Evolutionary Biology, 2007 Background The Bacteroidetes and Chlorobi species constitute two main groups of the Bacteria that are closely related in phylogenetic trees. The Bacteroidetes species are widely distributed and include many important periodontal pathogens.
Lorenzini Emily, Gupta Radhey S
doaj +1 more source
Recursive graphs with small-world scale-free properties
, 2004 We discuss a category of graphs, recursive clique trees, which have small-world and scale-free properties and allow a fine tuning of the clustering and the power-law exponent of their discrete degree distribution. We determine relevant characteristics of
A.-L. Barabási +20 more
core +1 more source
Tree-width, clique-minors, and eigenvalues
Discrete Mathematics, 2004 Let \(G\) be a simple graph of order \(n\). Let \(\rho(G)\) be the spectral radius of \(G\) and let \(\lambda(G)\) be the least eigenvalue of \(G\). The author proves the following results: If \(G\) is \(K_5\) minor-free graph, then \(\rho(G) \leq 1 + \sqrt{3n - 8}\), where equality holds if and only if \(G\) is isomorphic to \(K_3 \nabla (n-3)K_1 ...
openaire +2 more sources
Boundary cliques, clique trees and perfect sequences of maximal cliques of a chordal graph
, 2006 We characterize clique trees of a chordal graph in their relation to simplicial vertices and perfect sequences of maximal cliques. We investigate boundary cliques defined by Shibata and clarify their relation to endpoints of clique trees. Next we define a symmetric binary relation between the set of clique trees and the set of perfect sequences of ...
Hara, Hisayuki, Takemura, Akimichi
openaire +2 more sources
Partitioning the Bags of a Tree Decomposition into Cliques
, 2023 We consider a variant of treewidth that we call clique-partitioned treewidth in which each bag is partitioned into cliques. This is motivated by the recent development of FPT-algorithms based on similar parameters for various problems. With this paper, we take a first step towards computing clique-partitioned tree decompositions. Our focus lies on the
Bläsius, Thomas +2 more
openaire +6 more sources
Path Graphs, Clique Trees, and Flowers
, 2015 An \emph{asteroidal triple} is a set of three independent vertices in a graph such that any two vertices in the set are connected by a path which avoids the neighbourhood of the third. A classical result by Lekkerkerker and Boland \cite{6} showed that interval graphs are precisely the chordal graphs that do not have asteroidal triples.
Mouatadid, Lalla, Robere, Robert
openaire +2 more sources
An Introduction to Chordal Graphs and Clique Trees [PDF]
, 1993 Clique trees and chordal graphs have carved out a niche for themselves in recent work on sparse matrix algorithms, due primarily to research questions associated with advanced computer architectures. This paper is a unified and elementary introduction to the standard characterizations of chordal graphs and clique trees.
Jean R. S. Blair, Barry Peyton
openaire +5 more sources
Capturing Logarithmic Space and Polynomial Time on Chordal Claw-Free Graphs
, 2019 We show that the class of chordal claw-free graphs admits LREC$_=$-definable canonization. LREC$_=$ is a logic that extends first-order logic with counting by an operator that allows it to formalize a limited form of recursion.
Grußien, Berit
core +1 more source