
Minimal triangulations and potential maximal cliques are the main ingredients for a number of polynomial time algorithms on different graph classes computing the treewidth of a graph. Potential maximal cliques are also the main engine of the fastest so far O(1.9601^n)-time exact treewidth algorithm. Based on the recent results of Mazoit, we define the structures that can be regarded as minimal triangulations and potential maximal cliques for branchwidth: efficient triangulations and blocks. We show how blocks can be used to construct an algorithm computing the branchwidth of a graph on n vertices in time (2+√3)^n · n^O(1).
algorithm, Distance in graphs, exponential time algorithm, Applied Mathematics, efficient triangulations, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], graph, Graph, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Branchwidth, Graph algorithms (graph-theoretic aspects), Graph theory (including graph drawing) in computer science, Discrete Mathematics and Combinatorics, exponential algorithms, Exponential time algorithm, branchwidth
algorithm, Distance in graphs, exponential time algorithm, Applied Mathematics, efficient triangulations, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], graph, Graph, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Branchwidth, Graph algorithms (graph-theoretic aspects), Graph theory (including graph drawing) in computer science, Discrete Mathematics and Combinatorics, exponential algorithms, Exponential time algorithm, branchwidth
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 8 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
