389 citations · 1.1k across the 26 of their papers we have counts for
10 papers · 1 filter
Approximating the Graph Edit Distance with Compact Neighborhood Representations
Franka Bause, Christian Permann, Nils M. Kriege
The graph edit distance is used for comparing graphs in various domains. Due to its high computational complexity it is primarily approximated. Widely-used heuristics search for an…
Improved Exact and Heuristic Algorithms for Maximum Weight Clique
Roman Erhardt, Kathrin Hanauer, Nils Kriege +2
We propose improved exact and heuristic algorithms for solving the maximum weight clique problem, a well-known problem in graph theory with many applications. Our algorithms interl…
Maximum Cut Parameterized by Crossing Number
Markus Chimani, Christine Dahn, Martina Juhnke-Kubitzke +3
Given an edge-weighted graph on nodes, the NP-hard Max-Cut problem asks for a node bipartition such that the sum of edge weights joining the different partitions is maximiz…
Fixed-Parameter Algorithms for the Weighted Max-Cut Problem on Embedded 1-Planar Graphs
Christine Dahn, Nils M. Kriege, Petra Mutzel +1
We propose two fixed-parameter tractable algorithms for the weighted Max-Cut problem on embedded 1-planar graphs parameterized by the crossing number of the given embedding. A…
Largest Weight Common Subtree Embeddings with Distance Penalties
Andre Droschinsky, Nils M. Kriege, Petra Mutzel
The largest common embeddable subtree problem asks for the largest possible tree embeddable into two input trees and generalizes the classical maximum common subtree problem. Sever…
A note on block-and-bridge preserving maximum common subgraph algorithms for outerplanar graphs
Nils M. Kriege, Andre Droschinsky, Petra Mutzel
Schietgat, Ramon and Bruynooghe proposed a polynomial-time algorithm for computing a maximum common subgraph under the block-and-bridge preserving subgraph isomorphism (BBP-MCS) fo…
A Fixed-Parameter Algorithm for the Max-Cut Problem on Embedded 1-Planar Graphs
Christine Dahn, Nils M. Kriege, Petra Mutzel
We propose a fixed-parameter tractable algorithm for the \textsc{Max-Cut} problem on embedded 1-planar graphs parameterized by the crossing number of the given embedding. A gra…
On Maximum Common Subgraph Problems in Series-Parallel Graphs
Nils Kriege, Florian Kurpicz, Petra Mutzel
The complexity of the maximum common connected subgraph problem in partial -trees is still not fully understood. Polynomial-time solutions are known for degree-bounded outerplan…
A general purpose algorithm for counting simple cycles and simple paths of any length
Pierre-Louis Giscard, Nils Kriege, Richard C. Wilson
We describe a general purpose algorithm for counting simple cycles and simple paths of any length on a (weighted di)graph on vertices and edges, achieving a time com…
Finding Largest Common Substructures of Molecules in Quadratic Time
Andre Droschinsky, Nils Kriege, Petra Mutzel
Finding the common structural features of two molecules is a fundamental task in cheminformatics. Most drugs are small molecules, which can naturally be interpreted as graphs. Henc…