| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 10151235 | Discrete Applied Mathematics | 2018 | 11 Pages |
Abstract
We use these representations to compare mm-width with treewidth and branchwidth, and also to give another new characterization of mm-width, by subgraphs of chordal graphs. We prove that given a graph G and a branch decomposition of maximum matching width k we can solve the Minimum Dominating Set Problem in time Oâ(8k), thereby beating Oâ(3tw(G)) whenever tw(G)>log38Ãkâ1.893k. Note that mmw(G)â¤tw(G)+1â¤3mmw(G) and these inequalities are tight. Given only the graph G and using the best known algorithms to find decompositions, maximum matching width will be better for Minimum Dominating Set whenever tw(G)>1.549Ãmmw(G).
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Jisu Jeong, Sigve Hortemo Sæther, Jan Arne Telle,