Есть ли какие-либо алгоритмы онлайн для тестирования планарности?
Почему бы не работать regexp назад? Простой пример: если Ваш regexp
/[a-zA-Z]{6}/
тогда, Вы знаете, что нуждаетесь в 6 буквах a-z или A-Z, поэтому генерируете их. Это может стать более необычным, конечно, и, в зависимости от Ваших потребностей, можно закончить запись реверса весь regexp синтаксический анализатор, но можно прекратить добавлять опции при выполнении потребности.
1 ответ
После некоторых дополнительных исследований выяснилось, что ответ - «да», есть онлайн-алгоритмы, но «нет» их нет с амортизированным временем работы O (1).
Вот пример Статья 1999 г. в журнале ACM, Полное динамическое тестирование планарности с приложениями , в которой авторы написали:
В частности, мы рассматриваем следующие три операции на плоском графе G: (i) вставка ребро, если результирующий граф остается плоским; (ii) удалить ребро; и (iii) проверить, можно ли добавить ребро к графу без нарушения планарности. Мы покажем, как поддерживать каждую из вышеуказанных операций за время O (n ^ 2/3), где n - количество вершин в графе. Граница для тестов и удалений - наихудший случай, в то время как граница для вставок амортизируется.
Я также нашел отрывок из статьи 1989 года,