On finding spanning eulerian subgraphs

M. B. Richey, R. Gary Parker and R. L. Rardin

Naval Research Logistics Quarterly, 1985, vol. 32, issue 3, 443-455

Abstract: In this article, we examine the problem of producing a spanning Eulerian subgraph in an undirected graph. After the ℋ‐completeness of the general problem is established, we present polynomial‐time algorithms for both the maximization and minimization versions where instances are defined on a restricted class of graphs referred to as series‐parallel. Some novelties in the minimization case are discussed, as are heuristic ideas.

Date: 1985
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/nav.3800320308

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navlog:v:32:y:1985:i:3:p:443-455

Access Statistics for this article

More articles in Naval Research Logistics Quarterly from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().