Maximum packing for biconnected outerplanar graphs

DOI10.1016/S0166-218X(99)00176-6MaRDI QIDQ1962022zbMATH OpenOpenAlexFDO

Authors Tomas Kovacs, Andrzej Lingas

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

Recommendations

• Edge-packing in planar graphs
• Maximum packing for \(k\)-connected partial \(k\)-trees in polynomial time
• Maximum tree-packing in time \(O(n^{5/2})\)
• scientific article; zbMATH DE number 3963193
• Edge-packing planar graphs by cyclic graphs

Cites work

• scientific article; zbMATH DE number 4060712 (Why is no real title available?)
• scientific article; zbMATH DE number 4072379 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• Approximation algorithms for maximum two-dimensional pattern matching
• Characterizing the complexity of subgraph isomorphism for graphs of bounded path-width
• Easy problems for tree-decomposable graphs
• Faster algorithms for subgraph isomorphism of \(k\)-connected partial \(k\)-trees
• Generalized planar matching
• Introduction to algorithms
• Linear algorithms to recognize outerplanar and maximal outerplanar graphs
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Maximum tree-packing in time \(O(n^{5/2})\)
• On generalized matching problems
• On parallel complexity of the subgraph homeomorphism of the subgraph isomorphism problem for classes of planar graphs
• On the completeness of a generalized matching problem
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• Subgraph isomorphism for biconnected outerplanar graphs in cubic time
• Subtree Isomorphism in O(n5/2)
• The subgraph isomorphism problem for outerplanar graphs

Cited in

(2)

• Maximum packing for \(k\)-connected partial \(k\)-trees in polynomial time
• Outer-connected open packing sets in graphs

This page was built for publication: Maximum packing for biconnected outerplanar graphs

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