On finding spanning eulerian subgraphs

DOI10.1002/NAV.3800320308MaRDI QIDQ3703676zbMATH OpenOpenAlexFDO

Authors Michael B. Richey, R. G. Parker, Ronald L. Rardin

Publication date 1985

Published in Naval Research Logistics Quarterly (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/nav.3800320308

zbMATH Keywords

(connected) spanning Eulerian subgraphheuristic notionsNP- completenesspolynomial-time algorithmsseries-parallel graphsundirected graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Eulerian and Hamiltonian graphs (05C45) Analysis of algorithms and problem complexity (68Q25) Programming involving graphs or networks (90C35)

Recommendations

• A cubic algorithm for the directed Eulerian subgraph problem
• The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs
• On 3-edge-connected supereulerian graphs

Cites work

• Graph theory with applications

Cited in

(17)

• Minimum-maximal matching in series-parallel graphs
• Permutation graphs: Connected domination and Steiner trees
• Algorithms for recognition of regular properties and decomposition of recursive graph families
• Spanning eulerian subgraphs, the splitting lemma, and Petersen's theorem
• Minimum perfect bipartite matchings and spanning trees under categorization
• Weighted connected domination and Steiner trees in distance-hereditary graphs
• On minimum cuts and the linear arrangement problem
• Spanning Eulerian subgraphs of large size
• The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs
• Routing problems: A bibliography
• A note on the undirected rural postman problem polytope
• On computing the Hamiltonian index of graphs
• scientific article; zbMATH DE number 3628985 (Why is no real title available?)
• scientific article; zbMATH DE number 2177321 (Why is no real title available?)
• On Computing the Hamiltonian Index of Graphs
• scientific article; zbMATH DE number 6604940 (Why is no real title available?)
• A cubic algorithm for the directed Eulerian subgraph problem

This page was built for publication: On finding spanning eulerian subgraphs

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