Maximum packing for biconnected outerplanar graphs

DOI10.1016/S0166-218X(99)00176-6zbMath0944.05075OpenAlexW2105366839MaRDI QIDQ1962022

Andrzej Lingas, Tomas Kovacs

Publication date: 15 September 2000

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(99)00176-6

zbMATH Keywords

directed acyclic graphsmaximum packingbiconnected outerplanar graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Maximum packing for \(k\)-connected partial \(k\)-trees in polynomial time

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The subgraph isomorphism problem for outerplanar graphs
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Linear algorithms to recognize outerplanar and maximal outerplanar graphs
• On generalized matching problems
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• On parallel complexity of the subgraph homeomorphism of the subgraph isomorphism problem for classes of planar graphs
• Maximum tree-packing in time \(O(n^{5/2})\)
• Subgraph isomorphism for biconnected outerplanar graphs in cubic time
• Generalized planar matching
• Easy problems for tree-decomposable graphs
• Subtree Isomorphism in O(n5/2)
• Characterizing the complexity of subgraph isomorphism for graphs of bounded path-width
• Faster algorithms for subgraph isomorphism of κ-connected partial κ-trees
• On the completeness of a generalized matching problem
• Approximation algorithms for maximum two-dimensional pattern matching