A faster algorithm for the maximum even factor problem

DOI10.1007/978-3-642-17517-6_40MaRDI QIDQ3060755zbMATH OpenOpenAlexFDO

Authors Maxim Babenko

Publication date 9 December 2010

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1004.2115

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Abstract: Given a digraph $G=(VG,AG)$, an emph{even factor} $MsubseteqAG$ 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}logn)$-time algorithm for finding a maximum cardinality even factor in an odd-cycle symmetric digraph.

Recommendations

• Improved algorithms for even factors and square-free simple \(b\)-matchings
• A weighted even factor algorithm
• scientific article; zbMATH DE number 5888314
• The Independent Even Factor Problem
• scientific article; zbMATH DE number 6381750

Cited in

(5)

• Improved algorithms for even factors and square-free simple \(b\)-matchings
• A weighted independent even factor algorithm
• scientific article; zbMATH DE number 5888314 (Why is no real title available?)
• A Combinatorial Algorithm to Find a Maximum Even Factor
• A weighted even factor algorithm

This page was built for publication: A faster algorithm for the maximum even factor problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3060755)