A cubic algorithm for the directed Eulerian subgraph problem

DOI10.1016/0377-2217(91)90266-XMaRDI QIDQ806684zbMATH OpenFDO

Authors Michael B. Richey, R. G. Parker

Publication date 1991

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0377-2217(91)90266-X

zbMATH Keywords

cubic algorithmdirected Eulerian subgraph problemdirected graphdirected series-parallel graphsNP- hard

Mathematics Subject Classification ID

Computational methods for problems pertaining to operations research and mathematical programming (90-08) Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Review text

The authors discuss the problem to find for a given directed graph G(V,A) with arc weighted function w a maximum (arc)-weight subgraph of G which is Eulerian. The problem is NP-hard. The authors give a cubic-time algorithm for its resolution on directed series-parallel graphs.

Recommendations

• Exact Algorithms for Maximum Acyclic Subgraph on a Superclass of Cubic Graphs
• On the connected spanning cubic subgraph problem
• Pathwidth of cubic graphs and exact algorithms
• TSP on cubic and subcubic graphs
• Algorithm Theory - SWAT 2004
• An Improved Exact Algorithm for Cubic Graph TSP
• An algorithm for optimal acyclic edge-colouring of cubic graphs
• A polynomial time algorithm for cyclic vertex connectivity of cubic graphs
• Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Other Directed Network Design Problems
• Quasi-polynomial algorithms for submodular tree orienteering and directed network design problems

Cites work

• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• Efficient Algorithms for Optimization and Selection on Series-Parallel Graphs
• scientific article; zbMATH DE number 3737730 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On finding spanning eulerian subgraphs
• On multiple steiner subgraph problems
• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
• Topology of series-parallel networks

Cited in

(3)

• Routing problems: A bibliography
• On finding spanning eulerian subgraphs
• scientific article; zbMATH DE number 1784942 (Why is no real title available?)

This page was built for publication: A cubic algorithm for the directed Eulerian subgraph problem

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