Maximum packing for \(k\)-connected partial \(k\)-trees in polynomial time
From MaRDI portal
Publication:1978642
DOI10.1016/S0304-3975(99)00208-XzbMath0938.68143WikidataQ128024496 ScholiaQ128024496MaRDI QIDQ1978642
Andrzej Lingas, Andrzej Proskurowski, Anders Dessmark
Publication date: 4 June 2000
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of subgraph isomorphism for classes of partial k-trees
- Subtree isomorphism is NC reducible to bipartite perfect matching
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- On generalized matching problems
- On the complexity of finding iso- and other morphisms for partial \(k\)- trees
- Parallel concepts in graph theory
- Maximum tree-packing in time \(O(n^{5/2})\)
- Memory requirements for table computations in partial \(k\)-tree algorithms
- Subgraph isomorphism for biconnected outerplanar graphs in cubic time
- On simple characterizations of k-trees
- Maximum packing for biconnected outerplanar graphs
- Generalized planar matching
- Easy problems for tree-decomposable graphs
- Graph minors. II. Algorithmic aspects of tree-width
- 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
- A linear time algorithm for finding tree-decompositions of small treewidth
- On the completeness of a generalized matching problem
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs