302 citations · 303 across the 4 of their papers we have counts for
10 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…
On the Enumeration and Counting of Bicriteria Temporal Paths
Petra Mutzel, Lutz Oettershagen
We discuss the complexity of path enumeration and counting in weighted temporal graphs. In a weighted temporal graph, each edge has an availability time, a traversal time and some…
A new Integer Linear Program for the Steiner Tree Problem with Revenues, Budget and Hop Constraints
Adalat Jabrayilov, Petra Mutzel
The Steiner tree problem with revenues, budgets and hop constraints (STPRBH) is a variant of the classical Steiner tree problem. This problem asks for a subtree in a given graph wi…
A Flow Formulation for Horizontal Coordinate Assignment with Prescribed Width
Michael Jünger, Petra Mutzel, Christiane Spisla
We consider the coordinate assignment phase of the well known Sugiyama framework for drawing directed graphs in a hierarchical style. The extensive literature in this area has give…
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…