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

polynomial time algorithmisomorphism problemslink graphrecognizing link treesZykov problem

Mathematics Subject Classification ID

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

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)

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

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)