3 papers
cs.DS2020
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…
cs.DS2018
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…
cs.DS2018
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…