Teoretyczne informatyka graph-algorithms

2

Niech będzie wykresem. Niechbyć liczbą całkowitą. Niech będzie liczbą indukowanych przez krawędź posiadających wierzchołków i nieparzystą liczbę krawędzi. Niech będzie liczbą podgraphów indukowanych przez krawędź, mających wierzchołków i parzystą liczbę krawędzi. Niech . Problem ODD NAWET DELTA polega na obliczeniu , biorąc pod uwagę G i k .G = ( …

9 ds.algorithms graph-theory graph-algorithms counting-complexity

1

Czy istnieje odpowiedni algorytm do rysowania mieszanego wykresu okręgu / zależności w układzie współrzędnych?

Szukam algorytmu do rysowania mieszanego wykresu okręgów / zależności (dla aplikacji językowych). Taki wykres miałby dwa różne typy wierzchołków (tokeny, węzły) i dwa różne typy krawędzi (hierarchiczne, niehierarchiczne). Jestem nowy w teorii grafów i algorytmach w ogóle i mam nadzieję, że to pytanie nie koliduje np. Z wymaganiami dotyczącymi tej …

9 ds.algorithms graph-algorithms cg.comp-geom graph-drawing

2

Złożoność znalezienia separatora grafów o danej właściwości

Czy są znane wyniki na temat złożoności znalezienia separatora (dowolnej wielkości) spełniającego daną właściwość? Wiem, że separator kliki jest łatwy do znalezienia (czas wielomianowy), a także wiem, że wiele artykułów rozważa problem znalezienia małych separatorów lub separatorów, które pozostawiają połączone komponenty wielkości co najwyżej ułamka wielkości oryginalnego wykresu. Ale co, …

9 ds.algorithms graph-theory graph-algorithms

4

Treewidth i pakowanie

Moje pytanie jest trochę niejasne. Zastanawiam się, czy (i jak) możemy zastosować pojęcie szerokości do problemów z upakowaniem na wykresach. Byłbym zadowolony z wszelkich spostrzeżeń lub odniesień do wcześniejszych prac badawczych na ten temat (zakładając, że jest to jakaś relacja). Dzięki.

9 ds.algorithms reference-request graph-theory graph-algorithms approximation-algorithms

2

Wczesne referencje do dyskretnej optymalizacji

(Przepraszamy, jeśli jest to źle umieszczone lub zbyt szerokie. Jestem otwarty na sugestie, jak to przeformułować). Interesuje mnie prześledzenie „starożytnej” historii algorytmów maksymalnego przepływu i ogólnie dyskretnych algorytmów optymalizacji. Ford-Fulkerson jest moim słomkowym punktem wyjścia. Jakie były wcześniej znaczące postępy? Jak daleko możemy się cofnąć, wciąż będąc w stanie uzasadnić, …

9 ds.algorithms graph-algorithms ho.history-overview

2

Algorytm wyliczania kliki

Czytam stary artykuł MC Golumbica na temat wykresów EPT (przecięcie krawędzi ścieżek na drzewie). W artykule pokazano, że liczba maksymalnych klików wystąpienia wykresu EPT jest wielomianowa. Stwierdza, że jeśli wyrocznia zgłasza, że wykressolsolG jest wykresem EPT, możliwe jest znalezienie maksymalnej kliki za pomocą standardowego algorytmu wyliczania kliki. Po pierwsze, jakie …

9 ds.algorithms graph-algorithms clique

3

Znajdowanie wszystkich cykli

Mam skończony zestaw S.SS, funkcja fa: S→ Sf:S→Sf:S\to Soraz całkowite zamówienie <<< na S.SS. Chcę znaleźć liczbę różnych cykliS.SS. Dla danego elementu s ∈ Ss∈Ss\in S Mogę użyć algorytmu Floyda (lub Brenta itp.), Aby znaleźć długość cyklu, w którym powtarzały się aplikacje faff wysyła sssdo; przy odrobinie wysiłku mogę zidentyfikować …

9 graph-theory graph-algorithms

2

Wydajne algorytmy przeszukiwania kolekcji drzew

Mam duży zestaw danych o drzewach i chciałbym je przeszukać, określając treelet (połączony podgrupa). Kwerenda powinna zwrócić wszystkie wystąpienia treeline w zbiorze danych. Czy istnieją wydajne algorytmy do tego celu? Myślałem o czymś takim jak tablice sufiksów, jednak naiwne kodowanie drzew, ponieważ łańcuchy (przez ustaloną kolejność ich węzłów) nie będą …

9 graph-algorithms ds.data-structures tree graph-isomorphism string-search

2

Najkrótsze ścieżki uniemożliwiające każdą krawędź

Byłbym wdzięczny za wszelkie wskazówki lub warunki, które mogłyby doprowadzić mnie do właściwego kierunku. Mamy ukierunkowany wykres G = ( V, E)G=(V,E)G=(V,E) i długości lI jlijl_{ij} dla każdej krawędzi I jijijktóre można uznać za pozytywne. Istnieje specjalny węzeł początkowysss i węzeł końcowy ttt. Dla każdej krawędzi I jijij, chcielibyśmy obliczyć …

9 ds.algorithms reference-request graph-algorithms

2

Czy istnieje struktura danych umożliwiająca szybkie manipulowanie listami i zapytania dotyczące zamówień?

Mamy zestaw, LLL, list elementów z zestawu N= { 1 , 2 , 3 , . . . ,n}N={1,2,3,...,n}N = \{ 1, 2, 3, ..., n \}. Każdy element zNNN pojawia się na jednej liście w LLL. Szukam struktury danych, która może wykonać następujące aktualizacje: c o n c at(x,y)concat(x,y)concat(x, …

9 ds.algorithms graph-algorithms ds.data-structures

3

Jak mogę losowo wygenerować drzewa o ograniczonej wysokości?

W przypadku projektu, nad którym pracuję, powinienem wygenerować losowo rozciągające się drzewa o ograniczonej wysokości. Zasadniczo wykonuję następujące czynności: 1) Wygeneruj drzewo opinające 2) Sprawdź wykonalność, jeśli to możliwe, zachowaj ją. 1) Zaczynając od minimalnego drzewa opinającego (Prim'a lub Kruskala), dodaję nieistniejącą krawędź i to tworzy cykl, wykrywam ten cykl …

9 ds.algorithms graph-algorithms random-walks

3

Rozkład drzewa dla grafów płaskich

Najpierw zapytany na stronie math.SE bez odpowiedzi Załóżmy, że mam wykres płaski z osadzeniem planarnym, jak znaleźć rozkład drzewa? Jaki jest optymalny rozkład drzewa siatki kwadratowej -by- ? Nie do końca pewny, jak zdefiniować „optymalny”, ale powinien odróżniać rozkład z jedną dużą torbą od rozkładu z wieloma dużymi torbami.dddddd

9 ds.algorithms graph-theory graph-algorithms treewidth integer-lattice

1

Czy problem tworzenia kopii zapasowej NP jest kompletny?

Czy następujący problem decyzyjny NP-zupełny: Niech będzie nieukierowanym wykresem i dwiema liczbami całkowitymi. Czy można wybrać dla każdego wierzchołka dokładnie różnych sąsiadów, tak że żaden węzeł nie zostanie wybrany więcej niż razy.GGGb≤cb≤cb \le cGGGbbbccc Przypadek można rozwiązać dla dowolnego czasie wielomianowym, stosując maksymalne dopasowanie.b=1b=1b = 1ccc Motywacja: każdy węzeł chce …

9 cc.complexity-theory np-hardness graph-algorithms

Pytania otagowane jako graph-algorithms