2006 | OriginalPaper | Buchkapitel
Generation of Graphs with Bounded Branchwidth
verfasst von : Christophe Paul, Andrzej Proskurowski, Jan Arne Telle
Erschienen in: Graph-Theoretic Concepts in Computer Science
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Branchwidth is a connectivity parameter of graphs closely related to treewidth. Graphs of treewidth at most
k
can be generated algorithmically as the subgraphs of
k
-trees. n this paper, we investigate the family of edge-maximal graphs of branchwidth
k
, that we call
k
-branches. The
k
-branches are, just as the
k
-trees, a subclass of the chordal graphs where all minimal separators have size
k
. However, a striking difference arises when considering subgraph-minimal members of the family. Whereas
K
k
+ 1
is the only subgraph-minimal
k
-tree, we show that for any
k
≥7 a minimal
k
-branch having
q
maximal cliques exists for any value of
$q \not\in \{3,5\}$
, except for
k
=8,
q
=2. We characterize subgraph-minimal
k
-branches for all values of
k
. Our investigation leads to a generation algorithm, that adds one or two new maximal cliques in each step, producing exactly the
k
-branches.