On the complexity of labeled oriented trees

DOI10.1007/S12044-010-0011-6MaRDI QIDQ968053zbMATH OpenOpenAlexFDO

Authors Stephan Rosebrock

Publication date 3 May 2010

Published in Proceedings of the Indian Academy of Sciences. Mathematical Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s12044-010-0011-6

zbMATH Keywords

2-complexesasphericitycomplexitylabeled oriented trees

Mathematics Subject Classification ID

Trees (05C05) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Relations of low-dimensional topology with graph theory (57M15)

Review text

Komplexitätsbegriffe wurden angeregt durch denjenigen von S. V. Matveev für eine 3-Mannigfaltigkeit. Dieser ist die Minimalzahl der Ecken eines ``fast speziellen zweidimensionalen Kollabierretrakts. E. L. Pervova und S. G. Ivanov haben das Konzept für 2-Komplexe modifiziert, letzterer im Hinblick auf das Studium des Andrews-Curtis-Problems. Eine direkt zugängliche Version von Komplexität für von beschrifteten orientierten Graphen abgelesene Präsentationen (= LOGs), speziell im Baumfall (=LOTs), liegt der vorliegenden Arbeit zugrunde. Die Motivation ist in erster Linie, zu Aussagen über das Whiteheadsche Asphärizitätsproblem zu gelangen. So wird gezeigt, dass LOT-Präsentationen der Komplexität 2 einen asphärischen Komplex haben. Auch für gewisse Serien höherer Komplexität wird die Asphärizität erwiesen. Eine Abschätzung im Fall, dass der zugrunde liegende Graph ein (unterteiltes) Intervall ist, wurde inzwischen von Moritz Christmann (Frankfurt/M) auf beliebige LOTs verallgemeinert. Abschließend wird die Komplexität von Standard-Wirtingerpräsentationen für Torusknoten bestimmt.

Recommendations

• Computational Complexity of the Distance Constrained Labeling Problem for Trees (Extended Abstract)
• Efficient dominating sets in labeled rooted oriented trees
• An O\((n^{1.75})\) algorithm for \(L(2,1)\)-labeling of trees
• Optimal labellings of rooted directed trees
• A REFINEMENT FOR ORDERED LABELED TREES
• The \(L(h,1,1)\)-labelling problem for trees
• An $\mbox{O}(n^{1.75})$ Algorithm for L(2,1)-Labeling of Trees
• A linear time algorithm for L(2,1)-labeling of trees
• A Linear Time Algorithm for L(2,1)-Labeling of Trees
• A note on the parameterized complexity of unordered maximum tree orientation

Cites work

• Aspherical labelled oriented trees and knots
• Codes of m-complexity 1.
• Cohomology theory of groups with a single defining relation
• On adding relations to homotopy groups
• On the asphericity of regions in a 3-sphere
• Some remarks on a problem of J. H. C. Whitehead
• Spherical diagrams and labelled oriented trees
• The Whitehead conjecture -- an overview

Cited in

(5)

• scientific article; zbMATH DE number 6863837 (Why is no real title available?)
• A class of locally indicable LOT groups
• Aspherical word labeled oriented graphs and cyclically presented groups
• Spherical diagrams and labelled oriented trees
• On the unavoidability of oriented trees

This page was built for publication: On the complexity of labeled oriented trees

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