Name
Abstract | ||
|---|---|---|
The linear induced matching width (LMIM-width) of a graph is a width parameter defined by using the notion of branch-decompositions of a set function on ternary trees. In this paper we study output-polynomial enumeration algorithms on graphs of bounded LMIM-width and graphs of bounded local LMIM-width. In particular, we show that all 1-minimal and all 1-maximal -dominating sets, and hence all minimal dominating sets, of graphs of bounded LMIM-width can be enumerated with polynomial (linear) delay using polynomial space. Furthermore, we show that all minimal dominating sets of a unit square graph can be enumerated in incremental polynomial time. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/s00453-017-0289-1 | Algorithmica |
Keywords | Field | DocType |
Domination problem,Local linear MIM-width,Output-polynomial enumeration,Linear delay | Set function,Discrete mathematics,Combinatorics,Polynomial,Enumeration,PSPACE,Unit square,Time complexity,1-planar graph,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
80 | 2 | 0178-4617 |
Citations | PageRank | References |
2 | 0.38 | 23 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Petr A. Golovach | 1 | 766 | 83.25 |
| Pinar Heggernes | 2 | 845 | 72.39 |
| Mamadou Moustapha Kanté | 3 | 172 | 20.93 |
| Dieter Kratsch | 4 | 1957 | 146.89 |
| Sigve Hortemo Sæther | 5 | 23 | 4.07 |
| Yngve Villanger | 6 | 592 | 37.08 |