-
Latest research news
-
Parents should be allowed to make informed choices over infant bed-sharing, says child sleep expert
Parents should be given more information and be encouraged to make informed choices to minimise the risks of infant bed-sharing, a child sleep expert has said.
-
Brain frontal lobes not sole centre of human intelligence
Human intelligence cannot be explained by the size of the brain’s frontal lobes, say researchers.
-
Museum find proves exotic ‘big cat’ prowled British countryside a century ago
The rediscovery of a mystery animal in a museum’s underground storeroom proves that a non-native ‘big cat’ prowled the British countryside at the turn of the last century.
-
New fracking research led by Durham University finds it is “not significant” in causing earthquakes
A new study of hundreds of thousands of hydraulic fracturing (or “fracking”) operations has found that the process has only caused earth tremors that could be felt on the surface in three cases.
-
Research is at the core of Durham University. It shapes and inspires the disciplinary structure of our departments, several of which lead the UK - and even the world - in their fields. Research leads the content and development of our teaching at undergraduate and postgraduate levels, and creates new cross-disciplinary programmes through our centres and institutes. In partnership with policy-makers, industry, healthcare and education, Durham's cross-disciplinary and cross-cultural research shapes local, national and international agendas.
Links to recent research highlights and to the Research Office and other units and schemes that support our research can be found on this page.
Forthcoming research seminars
Minimal Dominating Sets in Graphs: Enumeration, Combinatorial Bounds and Graph Classes
In 2008 Fomin, Grandoni, Pyatkin and Stepanov provided an exact exponential time algorithm to enumerate all minimal dominating sets of a graph. Its main consequence was the first non trivial upper bound on the number of minimal dominating sets; the maximum number of minimal dominating sets that a graph on n vertices can have is at most 1.7159^n. This upper bound might not be tight, since no examples of graphs with 1.5705^n or more minimal dominating sets are known.
This talk considers exact exponential algorithms to enumerate minimal dominating sets when the input graphs are restricted to certain graph classes, among them chordal graphs, cographs and chain graphs. The following types of results exploiting the structure of the particular graph classes are presented: (i) enumeration algorithms based on branching algorithms and their analysis via upper bounding the number of leaves in search trees, (ii) upper bounds on the maximum number of minimal dominating sets in n-vertex graphs obtained via branching algorithms or combinatorial proofs, (iii) lower bounds on the maximum number of minimal dominating sets. In some cases, we provide examples of graphs whose number of minimal dominating sets exactly matches the proved upper bound for that class, thereby showing that these bounds are tight.
Contact daniel.paulusma@durham.ac.uk for more information about this event.
Download this event in iCalendar format
Breakthrough
Visit Durham's brand new research microsite - Breakthrough - for examples of our latest research, outstanding achievements and research grants.
Want to find out more about research at Durham?
Find out what's going on around the University in your research area
- Research seminars and events
- Durham Research Online (articles, chapters and papers)
- Researchers in your field