7 citations · 9 across the 8 of their papers we have counts for
6 papers · 1 filter
A General Approach to Approximate Multistage Subgraph Problems
Markus Chimani, Niklas Troost, Tilo Wiedera
In a Subgraph Problem we are given some graph and want to find a feasible subgraph that optimizes some measure. We consider Multistage Subgraph Problems (MSPs), where we are given…
An Experimental Study of ILP Formulations for the Longest Induced Path Problem
Fritz Bökler, Markus Chimani, Mirko H. Wagner +1
Given a graph , the longest induced path problem asks for a maximum cardinality node subset such that the graph induced by is a path. It is a long estab…
Approximating Multistage Matching Problems
Markus Chimani, Niklas Troost, Tilo Wiedera
In multistage perfect matching problems we are given a sequence of graphs on the same vertex set and asked to find a sequence of perfect matchings, corresponding to the sequence of…
Cycles to the Rescue! Novel Constraints to Compute Maximum Planar Subgraphs Fast
Markus Chimani, Tilo Wiedera
The NP-hard Maximum Planar Subgraph problem asks for a planar subgraph of a given graph such that has maximum edge cardinality. For more than two decades, the only know…
Exact Algorithms for the Maximum Planar Subgraph Problem: New Models and Experiments
Markus Chimani, Ivo Hedtke, Tilo Wiedera
Given a graph , the NP-hard Maximum Planar Subgraph problem asks for a planar subgraph of with the maximum number of edges. The only known non-trivial exact algorithm utiliz…
A Note on the Practicality of Maximal Planar Subgraph Algorithms
Markus Chimani, Karsten Klein, Tilo Wiedera
Given a graph , the NP-hard Maximum Planar Subgraph problem (MPS) asks for a planar subgraph of with the maximum number of edges. There are several heuristic, approximative,…