Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: On the maximum number of minimal connected dominating sets in convex
  bipartite graphs   The enumeration of minimal connected dominating sets is known to be
notoriously hard for general graphs. Currently, it is only known that the sets
can be enumerated slightly faster than $\mathcal{O}^{*}(2^n)$ and the algorithm
is highly nontrivial. Moreover, it seems that it is hard to use bipartiteness
as a structural aide when constructing enumeration algorithms. Hence, to the
best of our knowledge, there is no known input-sensitive algorithm for
enumerating minimal dominating sets, or one of their related sets, in bipartite
graphs better than that of general graphs. In this paper, we provide the first
input-sensitive enumeration algorithm for some non trivial subclass of
bipartite graphs, namely the convex graphs. We present an algorithm to
enumerate all minimal connected dominating sets of convex bipartite graphs in
time $\mathcal{O}(1.7254^{n})$ where $n$ is the number of vertices of the input
graph. Our algorithm implies a corresponding upper bound for the number of
minimal connected dominating sets for this graph class. We complement the
result by providing a convex bipartite graph, which have at least $3^{(n-2)/3}$
minimal connected dominating sets.

3
The categories of this paper are: physics
15
The categories of this paper are: nucl-ex
28
The categories of this paper are: alg-geom
8
The categories of this paper are: hep-ex
9
The categories of this paper are: nlin
36
The categories of this paper are: cmp-lg
4
The categories of this paper are: cond-mat
18
The categories of this paper are: econ
11
The categories of this paper are: hep-lat
0
The categories of this paper are: hep-ph
25
The categories of this paper are: patt-sol
32
The categories of this paper are: atom-ph
26
The categories of this paper are: bayes-an
30
The categories of this paper are: q-alg
19
The categories of this paper are: eess
14
The categories of this paper are: math-ph