A cubic algorithm for the directed Eulerian subgraph problem

A cubic algorithm for the directed Eulerian subgraph problem

0.00 Avg rating—0 Votes
Article ID: iaor1993615
Country: Netherlands
Volume: 50
Issue: 3
Start Page Number: 345
End Page Number: 352
Publication Date: Feb 1991
Journal: European Journal of Operational Research
Authors: ,
Keywords: optimization, combinatorial analysis
Abstract:

Given a directed graph G(V,A) with arcs weighted as w:A⇒Z, the authors seek a maximum (arc) weight subgraph of G which is Eulerian. After showing the problem to be NP-hard even on graphs with bounded vertex degree, they give a cubic-time algorithm for its resolution on directed series-parallel graphs.

Reviews

Required fields are marked *. Your email address will not be published.