A Faster Algorithm for the Maximum Even Factor Problem

Details A Faster Algorithm for the Maximum Even Factor Problem A Faster Algorithm for the Maximum Even Factor Problem

2010-04-13

arxiv.org/abs/1004.2115v2

Mathematics

Combinatorics

Scientific paper

Given a digraph $G = (VG,AG)$, an \emph{even factor} $M \subseteq AG$ is a subset of arcs that decomposes into a collection of node-disjoint paths and even cycles. Even factors in digraphs were introduced by Geleen and Cunningham and generalize path matchings in undirected graphs. Finding an even factor of maximum cardinality in a general digraph is known to be NP-hard but for the class of \emph{odd-cycle symmetric} digraphs the problem is polynomially solvable. So far, the only combinatorial algorithm known for this task is due to Pap; it has the running time of $O(n^4)$ (hereinafter $n$ stands for the number of nodes in $G$). In this paper we present a novel \emph{sparse recovery} technique and devise an $O(n^3 \log n)$-time algorithm for finding a maximum cardinality even factor in an odd-cycle symmetric digraph.

Affiliated with

Also associated with

No associations

Rating

A Faster Algorithm for the Maximum Even Factor Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Faster Algorithm for the Maximum Even Factor Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Faster Algorithm for the Maximum Even Factor Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-281502