Search

Your search keyword '"Frank Dehne"' showing total 203 results
Start Over Author "Frank Dehne"
203 results on '"Frank Dehne"'

201. Polynomial Delay Algorithm for Listing Minimal Edge Dominating Sets in Graphs

Author

Lhouari Nourine, Takeaki Uno, Mamadou Moustapha Kanté, Arnaud Mary, Vincent Limouzy, Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes (LIMOS), SIGMA Clermont (SIGMA Clermont)-Université d'Auvergne - Clermont-Ferrand I (UdA)-Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Blaise Pascal - Clermont-Ferrand 2 (UBP), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Baobab, Département PEGASE [LBBE] (PEGASE), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), National Institute of Informatics (NII), Frank Dehne, Jörg-Rüdiger Sack, Ulrike Stege, and Université Blaise Pascal - Clermont-Ferrand 2 (UBP)-Université d'Auvergne - Clermont-Ferrand I (UdA)-SIGMA Clermont (SIGMA Clermont)-Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)

Subjects
FOS: Computer and information sciences, 68R05, 68R10, 05C30, 05C69, 05C76, 05C85, Existential quantification, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Structure (category theory), G.2.2, 0102 computer and information sciences, 01 natural sciences, law.invention, Combinatorics, law, Dominating set, Computer Science - Data Structures and Algorithms, F.0, Line graph, Enumeration, Permutation graph, Data Structures and Algorithms (cs.DS), 0101 mathematics, Mathematics, PSPACE, Discrete mathematics, 010102 general mathematics, 16. Peace & justice, 010201 computation theory & mathematics, Enhanced Data Rates for GSM Evolution, Algorithm, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

The Transversal problem, i.e, the enumeration of all the minimal transversals of a hypergraph in output-polynomial time, i.e, in time polynomial in its size and the cumulated size of all its minimal transversals, is a fifty years old open problem, and up to now there are few examples of hypergraph classes where the problem is solved. A minimal dominating set in a graph is a subset of its vertex set that has a non empty intersection with the closed neighborhood of every vertex. It is proved in [M. M. Kant\'e, V. Limouzy, A. Mary, L. Nourine, On the Enumeration of Minimal Dominating Sets and Related Notions, In Revision 2014] that the enumeration of minimal dominating sets in graphs and the enumeration of minimal transversals in hypergraphs are two equivalent problems. Hoping this equivalence can help to get new insights in the Transversal problem, it is natural to look inside graph classes. It is proved independently and with different techniques in [Golovach et al. - ICALP 2013] and [Kant\'e et al. - ISAAC 2012] that minimal edge dominating sets in graphs (i.e, minimal dominating sets in line graphs) can be enumerated in incremental output-polynomial time. We provide the first polynomial delay and polynomial space algorithm that lists all the minimal edge dominating sets in graphs, answering an open problem of [Golovach et al. - ICALP 2013]. Besides the result, we hope the used techniques that are a mix of a modification of the well-known Berge's algorithm and a strong use of the structure of line graphs, are of great interest and could be used to get new output-polynomial time algorithms., Comment: proofs simplified from previous version, 12 pages, 2 figures

Published
2015

202. On the Area Requirements of Euclidean Minimum Spanning Trees

Author

Claudio Squarcella, Marco Chiesa, Michael Kaufmann, Patrizio Angelini, Fabrizio Frati, Till Bruckdorfer, Angelini, Patrizio, Bruckdorfer, Till, Chiesa, Marco, Frati, Fabrizio, Kaufmann, Michael, Squarcella, Claudio, Frank Dehne, John Iacono, Jorg-Rudiger Sack, Bruckdorfer, T, and Kaufmann, M

Subjects
Discrete mathematics, Control and Optimization, Spanning tree, Shortest-path tree, Minimum spanning tree, k-minimum spanning tree, Computer Science Applications, Distributed minimum spanning tree, Combinatorics, Computational Mathematics, Computational Theory and Mathematics, Kruskal's algorithm, TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, Euclidean minimum spanning tree, Reverse-delete algorithm, Geometry and Topology, Minimum degree spanning tree, MathematicsofComputing_DISCRETEMATHEMATICS, Mathematics
Abstract

In their seminal paper on Euclidean minimum spanning trees [Discrete & Computational Geometry, 1992], Monma and Suri proved that any tree of maximum degree 5 admits a planar embedding as a Euclidean minimum spanning tree. Their algorithm constructs embeddings with exponential area; however, the authors conjectured that cn × cn area is sometimes required to embed an n-vertex tree of maximum degree 5 as a Euclidean minimum spanning tree, for some constant c > 1. In this paper, we prove the first exponential lower bound on the area requirements for embedding trees as Euclidean minimum spanning trees.

Published
2014

203. Computing a Minimum-Depth Planar Graph Embedding in O(n^4) Time

Author

Maurizio Patrignani, Giuseppe Di Battista, Patrizio Angelini, Frank Dehne, Joerg-Ruediger Sack, Norbert Zeh, Angelini, Patrizio, DI BATTISTA, Giuseppe, and Patrignani, Maurizio

Subjects
Discrete mathematics, Book embedding, Planar straight-line graph, Graph embedding, Butterfly graph, Planar graph, Combinatorics, symbols.namesake, Outerplanar graph, Graph minor, symbols, Polyhedral graph, Mathematics, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

Consider an n-vertex planar graph G. We present an O(n^4)-time algorithm for computing an embedding of G with minimum distance from the external face. This bound improves on the best previous bound by an O(n log(n)) factor. As a side effect, our algorithm improves the bounds of several algorithms that require the computation of a minimum depth embedding.

Published
2007

Catalog

Books, media, physical & digital resources
See catalog results