Efficient computation of optimal temporal walks under waiting-time constraints

Autor: Matthias Bentert, Anne-Sophie Himmel, André Nichterlein, Rolf Niedermeier

Publikováno v: Applied Network Science, Vol 5, Iss 1, Pp 1-26 (2020)

Abstract Node connectivity plays a central role in temporal network analysis. We provide a broad study of various concepts of walks in temporal graphs, that is, graphs with fixed vertex sets but arc sets changing over time. Taking into account the te

Externí odkaz: https://doaj.org/article/116ed47d2ac14f05a48cc8dbe4f37f2f

Detecting and enumerating small induced subgraphs in c-closed graphs

Autor: André Nichterlein, Tomohiro Koana

Publikováno v: Discrete Applied Mathematics. 302:198-207

Fox et al. (2020) introduced a new parameter, called c -closure, for a parameterized study of clique enumeration problems. A graph G is c -closed if every pair of vertices with at least c common neighbors is adjacent. The c -closure of G is the small

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::9bfc58f1f0158e30be129fe3da67a9b4
https://doi.org/10.1016/j.dam.2021.06.019

On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering

Autor: André Nichterlein, Rolf Niedermeier, Anne-Sophie Himmel, Aleksander Figiel

Publikováno v: Lecture Notes in Computer Science ISBN: 9783030752415
CIAC

Editing a graph into a disjoint union of clusters is a standard optimization task in graph-based data clustering. Here, complementing classic work where the clusters shall be cliques, we focus on clusters that shall be 2-clubs, that is, subgraphs of

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::255e8edb701fd547bd60314cd76adf36
https://doi.org/10.1007/978-3-030-75242-2_15

The power of linear-time data reduction for maximum matching

Autor: André Nichterlein, George B. Mertzios, Rolf Niedermeier

Publikováno v: Algorithmica, 2020, Vol.82(12), pp.3521-3565 [Peer Reviewed Journal]
Larsen, Kim G. & Bodlaender, Hans L. & Raskin, Jean-Francois (Eds.). (2017). 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) : August 21-25, 2017, Aalborg (Denmark) ; proceedings. Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, pp. 46, LIPIcs–Leibniz International Proceedings in Informatics(83)

Finding maximum-cardinality matchings in undirected graphs is arguably one of the most central graph primitives. For m-edge and n-vertex graphs, it is well-known to be solvable in $$O(m\sqrt{n})$$ O ( m n ) time; however, for several applications thi

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::639342f22e256b0d0b20bd61295eeff4
https://doi.org/10.1007/s00453-020-00736-0

A Parameterized Algorithmics Framework for Degree Sequence Completion Problems in Directed Graphs

Autor: Marcelo Garlet Millani, André Nichterlein, Rolf Niedermeier, Robert Bredereck, Vincent Froese, Marcel Koseler

Publikováno v: Algorithmica. 81:1584-1614

There has been intensive work on the parameterized complexity of the typically NP-hard task to edit undirected graphs into graphs fulfilling certain given vertex degree constraints. In this work, we lift the investigations to the case of directed gra

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b7ca5710f46e4fac979c8287313bde15
https://doi.org/10.1007/s00453-018-0494-6