Výsledky vyhledávání

Efficient Recognition of Subgraphs of Planar Cubic Bridgeless Graphs

Autor: Goetze, Miriam, Jungeblut, Paul, Ueckerdt, Torsten

It follows from the work of Tait and the Four-Color-Theorem that a planar cubic graph is 3-edge-colorable if and only if it contains no bridge. We consider the question of which planar graphs are subgraphs of planar cubic bridgeless graphs, and hence

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3624606a7397a7fe99558ad93d30bb94
http://arxiv.org/abs/2204.11750

Zobrazit plný text záznamu

Akademický článek

Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.

Planar Graph Isomorphism Is in Log-Space

Autor: Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner

Publikováno v: Datta, S, Limaye, N, Nimbhorkar, P, Thierauf, T & Wagner, F 2022, ' Planar Graph Isomorphism Is in Log-Space ', ACM Transactions on Computation Theory, vol. 14, no. 2, pp. 1-33 . https://doi.org/10.1145/3543686
IEEE Conference on Computational Complexity

Graph Isomorphism is the prime example of a computational problem with a wide difference between the best known lower and upper bounds on its complexity. There is a significant gap between extant lower and upper bounds for planar graphs as well. We b

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0f037a799bea4b34835f550acbfad138
https://pure.itu.dk/portal/da/publications/f73e611b-6bcc-40e5-8ede-12f8e2b754e1

Zobrazit plný text záznamu

Three-in-a-tree in near linear time

Autor: Kai-Yuan Lai, Hsueh-I Lu, Mikkel Thorup

Publikováno v: Lai, K Y, Lu, H I & Thorup, M 2020, Three-in-a-tree in near linear time . in K Makarychev, Y Makarychev, M Tulsiani, G Kamath & J Chuzhoy (eds), STOC 2020-Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing . Association for Computing Machinery, Proceedings of the Annual ACM Symposium on Theory of Computing, pp. 1279-1292, 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, United States, 22/06/2020 . https://doi.org/10.1145/3357713.3384235
STOC

The three-in-a-tree problem is to determine if a simple undirected graph contains an induced subgraph which is a tree connecting three given vertices. Based on a beautiful characterization that is proved in more than twenty pages, Chudnovsky and Seym

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ab32fe69b2f0153bfd2943d08c795d69
https://curis.ku.dk/portal/da/publications/threeinatree-in-near-linear-time(4c671166-7394-4191-97f3-7ae2d34da5ba).html

Zobrazit plný text záznamu

An alternative method for refined process structure trees (RPST)

Autor: Yongsun Choi, Pauline Kongsuwan, N. Long Ha, Kwan Hee Han

Publikováno v: Business Process Management Journal. 26:613-629

Purpose The refined process structure tree (RPST), the hierarchy of non-overlapping single-entry single-exit (SESE) regions of a process model, has been utilized for better comprehension and more efficient analysis of business process models. Existin

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::22a670e2b3b2dab1714ffd93cc960137
https://doi.org/10.1108/bpmj-11-2018-0319

Zobrazit plný text záznamu

Drawing Planar Graphs

Autor: Md. Rezaul Karim, Md. Saidur Rahman

Publikováno v: WALCOM: Algorithms and Computation ISBN: 9783030398804
WALCOM

A graph is planar if it can be drawn or embedded in the plane so that no two edges intersect geometrically except at a vertex to which they are both incident. A plane graph is a planar graph with a fixed planar embedding in the plane. A drawing probl

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::71d34d3431d4ba03c50552978f3511e2
https://doi.org/10.1007/978-3-030-39881-1_1

Zobrazit plný text záznamu

An SPQR-tree-like embedding representation for level planarity

Autor: Brückner, Guido, Rutter, Ignaz

An SPQR-tree is a data structure that efficiently represents all planar embeddings of a biconnected planar graph. It is a key tool in a number of constrained planarity testing algorithms, which seek a planar embedding of a graph subject to some given

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3faa7f94ddfb3f74848675282ae864bd

Zobrazit plný text záznamu

Using SPQR-trees to speed up recognition algorithms based on 2-cutsets

Autor: H.B. de Macedo Filho, Raphael C. S. Machado, Z. Li, C.M.H. de Figueiredo

Publikováno v: Discrete Applied Mathematics. 245:101-108

Several well-studied classes of graphs admit structural characterizations via proper 2-cutsets which lead to polynomial-time recognition algorithms. The algorithms so far obtained for those recognition problems do not guarantee linear-time complexity

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::42cad304df25c8eff2346cb74b0daa64
https://doi.org/10.1016/j.dam.2017.01.009

Zobrazit plný text záznamu

Vyhledávací nástroje:

Upřesnit hledání