Pytania otagowane jako cliquewidth

1
Cliquewidth of Almost Cographs
( Wysłałem to pytanie do MathOverflow dwa tygodnie temu, ale jak dotąd bez ścisłej odpowiedzi) Mam pytanie dotyczące miar szerokości wykresu niekierowanych prostych wykresów. Powszechnie wiadomo, że wykresy (wykresy, które można budować za pomocą operacji rozłącznego łączenia i uzupełniania, poczynając od izolowanych wierzchołków) mają najwyżej 2-krotność (Courcelle i in., Górne …
1
Wyrażenia o szerokości kliki z głębokością logarytmiczną
Kiedy otrzymujemy rozkład drzewa wykresu o szerokości , istnieje kilka sposobów, dzięki którym możemy go uczynić „ładnym”. W szczególności wiadomo, że można go przekształcić w rozkład drzewa, w którym drzewo jest binarne, a jego wysokość wynosi . Można to osiągnąć przy zachowaniu szerokości rozkładu co najwyżej . (Patrz np. „Algorytmy …
1
Modułowy rozkład i szerokość kliki
Próbuję zrozumieć niektóre pojęcia dotyczące rozkładu modułowego i wykresów szerokości kliki . W tym artykule („Na wykresach uporządkowanych za pomocą P4”) znajduje się dowód na to, jak rozwiązać problemy z optymalizacją, takie jak liczba kliki lub liczba chromatyczna za pomocą rozkładu modułowego. Rozwiązanie tych problemów przez skomponowanie (przy użyciu sumy …
2
Problemy z optymalizacją MSOL na wykresach ograniczonej płynności z predykatami liczności
CMSOL to zliczanie logiki monadycznej drugiego rzędu, tj. Logiki grafów, w których domeną jest zestaw wierzchołków i krawędzi, istnieją predykaty dla przylegania wierzchołków i wierzchołków oraz występowania krawędzi i wierzchołków, istnieje kwantyfikacja na krawędziach, wierzchołkach, zestawach krawędzi i wierzchołkach ustawia, a istnieje predykat która wyraża, czy rozmiar S jest n …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.