A polynomial time algorithm recognizing link trees

DOI10.1002/JGT.3190190314MaRDI QIDQ4698091zbMATH OpenOpenAlexFDO

Authors

Publication date 14 May 1995

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/jgt.3190190314

zbMATH Keywords

isomorphism problemslink graphpolynomial time algorithmrecognizing link treesZykov problem

Mathematics Subject Classification ID

Trees (05C05) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A polynomial-time algorithm to find a linkless embedding of a graph
• scientific article; zbMATH DE number 4110715
• Graphs with constant link and small degree or order
• Characterization and Recognition of Partial 3-Trees
• Graphs with given group and given constant link

Cited in

(7)

• A polynomial-time algorithm to find a linkless embedding of a graph
• Trahtenbrot-Zykov problem and NP-completeness
• Polynomial time recognition of vertices contained in all (or no) maximum dissociation sets of a tree
• On extremal sizes of locally \(k\)-tree graphs.
• Bicycles and Spanning Trees
• scientific article; zbMATH DE number 4110715 (Why is no real title available?)
• scientific article; zbMATH DE number 1839455 (Why is no real title available?)

This page was built for publication: A polynomial time algorithm recognizing link trees

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