389 citations · 1.1k across the 26 of their papers we have counts for
5 papers · 1 filter
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…
Recognizing Cuneiform Signs Using Graph Based Methods
Nils M. Kriege, Matthias Fey, Denis Fisseler +2
The cuneiform script constitutes one of the earliest systems of writing and is realized by wedge-shaped marks on clay tablets. A tremendous number of cuneiform tablets have already…
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…