Instituts-Logo Theorie der Informatik
Prof. Dr. Isolde Adler
Institut für Informatik
Goethe-Universität
Frankfurt am Main

Isolde Adler's publications


Obstructions for linear rankwidth at most 1, with Arthur Farley and Andrzej Proskurowski.
Discrete Applied Mathematics, 168: 3-13, 2014.
Preliminary version: arXiv:1106.2533, 2011.

Interpreting nowhere dense graph classes as a classical notion of model theory, with Hans Adler.
European Journal of Combinatorics, 36:322-330, 2014.
Preliminary version: Nowhere dense graph classes, stability, and the independence property,
arXiv:1011.4016, 2010.

Linear Rank-Width and Linear Clique-Width of Trees, with Mamadou Kanté.
In 39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'13), Lecture Notes in Computer Science, pp 12-25, 2013.

Hypertree-depth and minors in hypergraphs, with Tereza Tereza Klimošová and Tomáš Gavenčiak.
Theor. Comput. Sci. 463: 84-95, 2012.

Planar Disjoint-Paths Completion, with Stavros Kolliopoulos and Dimitrios Thilikos.
Parameterized and Exact Computation - 6th International Symposium, IPEC 2011: 80-93.

Tight bounds for linkages in planar graphs, with Stavros Kolliopoulos, Philipp Krause, Daniel Lokshtanov, Saket Saurabh, and Dimitrios Thilikos.
ICALP 2011, 38th International Colloquium on Automata, Languages and Programming, pp 110-121, Lecture Notes in Computer Science, 2011.

A lower bound for the tree-width of planar graphs with vital linkages, with Philipp Krause.
arXiv:1011.2136, 2010

Fast minor testing in planar graphs, with Frederic Dorn, Fedor Fomin, Ignasi Sau, and Dimitrios Thilikos.
ESA 2010, 18th Annual European Symposium on Algorithms, pp. 97-109, Lecture Notes in Computer Science, 2010.
Full version in Algorithmica 64(1): 69-84, 2012.

On the boolean-width of a graph: structure and applications, with Binh-Minh Bui-Xuan, Yuri Rabinovich, Gabriel Renault, Jan Arne Telle and Martin Vatshelle.
Proceedings of the 36th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'10), Lecture Notes in Computer Science, 2010.

Faster parameterized algorithms for minor containment, with Frederic Dorn, Fedor Fomin, Ignasi Sau, and Dimitrios Thilikos.
Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT'10), Lecture Notes in Computer Science, pp. 322-333, 2010.
Full version in Theor. Comput. Sci. 412(50): 7018-7028, 2011.

Tree-width for first order formulae, with Mark Weyer.
Proceedings of the 23rd International Workshop on Computer Science Logic (CSL'09), Lecture Notes in Computer Science, pp.71-85, 2009.
Full version on arXiv:1203.3814v1, full version in Logical Methods in Computer Science 8(1): 2012.

Games for width parameters and monotonicity
arXiv:0906.3857, 2009.

A note on clique-width and tree-width for structures, with Hans Adler.
arXiv:0806.0103, 2008.
This is an updated version of the original note in German
Notiz zur unären Cliquenweite von Strukturen, 2005.

Tree-width and functional dependencies in databases
In: Proceedings of the 27th ACM Sigact-Sigart Symposium on Principles of Database Systems, (PODS'08), 311-320, 2008.

Computing Excluded Minors, with Martin Grohe and Stephan Kreutzer.
In Proceedings of the of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'08), pp.641-650, 2008.

Tree-related widths of graphs and hypergraphs
SIAM Journal on Discrete Mathematics, Volume 22(1), pp.102-123, 2008.

Directed Tree-Width Examples
Journal of Combinatorial Theory, Series B, Volume 97(5), pp.718-725, 2007.

Width functions for hypertree decompositions
PhD thesis, Freiburg 2006.

Marshals, Monotone Marshals, and Hypertree-Width
Journal of Graph Theory, 47(4):275--296, 2004.

Hypertree-Width and Related Hypergraph Invariants, with Georg Gottlob and Martin Grohe.
Conference version in Proceedings of the 3rd European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB'05),
DMTCS Proceedings Series, Volume AE, pp.5-10, 2005.
Full version in: European Journal of Combinatorics, Volume 28(8), pp.2167-2181, 2007.

Spiele als Hilfsmittel zu Strukturuntersuchungen bei Graphen und Hypergraphen
Diploma thesis (in german), Freiburg 2002.

Selected Talks


A few things about linear rank-width
A talk given at the Dagstuhl Seminar on Graph Modification Problems, February 2014.

The VC dimension of definable sets in graph classes
A talk given at 18. Jahrestagung der GI-Fachgruppe Logik in der Informatik, Ilmenau, November 2011.

Tight bounds for linkages in planar graphs
A talk given at ICALP, Zürich, July 2011.

Interpreting nowhere dense graph classes as a classical notion from model theory
A talk given at the meeting on Algorithmic Model Theory, AlMoTh, Leipzig, February 2011.

Algorithms in Graph Minors: Improving the Parameter Dependency
A talk given at the meeting on Graph Decomposition, Theory, Logics and Algorithms in the CIRM, Marseille, October 2010.

Boolean width of random graphs
A talk given at the CSL workshop on Logic, Combinatorics and Computation in Brno, August 2010.

On the Boolean width of graphs: structure and applications
A talk given at WG, June 2010.

Model Checking using tree-width methods - old and new
A talk given in Haifa, March 2010.

Tree-width and functional dependencies in databases
A talk given at PODS 2008 in Vancouver.

Computing excluded minors
A talk given at the Dagstuhl workshop "Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs" July 2007.

Hypertree-width and related invariants
A talk given at the CSL workshop on Logic and Combinatorics 2006 in Szeged.

Miscellaneous


Open problems related to computing obstruction sets
A small collection of open problems compiled for the workshop Graph Minors in Banff, Canada, 2008.


Last modified: Mar 7, 09:15:55 CET 2014