Baumweite ist ein nützliches Werkzeug, um schwierige Probleme auf Graphen effizient lösen zu können. Da das Bestimmen der Baumweite eines gegebenen Graphen G allgemein NP-schwer ist, sind schnell zu bestimmende und gleichzeitig möglichst gute Approximationen wünschenswert. Entsprechend überrascht es nicht, dass sich in den letzten Jahren viele Arbeiten den diversen Seiten der Baumweite gewidmet haben. Ziel ist es nun, eine mit der Baumweite verwandte Größe vorzustellen und zu untersuchen - die Boolsche Weite. Skryť popis