Algorithms for recognition of regular properties and decomposition of recursive graph families

DOI10.1007/BF02115752zbMath0739.05078OpenAlexW2003212196MaRDI QIDQ1179734

R. Gary Parker, Craig A. Tovey, Richard B. Borie

Publication date: 27 June 1992

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02115752

zbMATH Keywords

linear time algorithmHalin graphsrecursively definable graph classesseries-parallel operations

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

On Halin subgraphs and supergraphs, Fast searching games on graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Minimum-maximal matching in series-parallel graphs
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Topology of series-parallel networks
• Steiner trees, partial 2–trees, and minimum IFI networks
• Easy problems for tree-decomposable graphs
• On finding spanning eulerian subgraphs
• An efficiently solvable case of the minimum weight equivalent subgraph problem
• Complexity of Finding Embeddings in a k-Tree
• Graph expressions and graph rewritings
• On multiple steiner subgraph problems
• Linear-time computability of combinatorial problems on series-parallel graphs
• Linear-time computation of optimal subgraphs of decomposable graphs