Výsledky vyhledávání

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.

Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering

Autor: Daniel Lokshtanov, Michał Pilipczuk, Saket Saurabh, Fedor V. Fomin, Marcin Pilipczuk, Dániel Marx

Publikováno v: FOCS

We prove the following theorem. Given a planar graph $G$ and an integer $k$, it is possible in polynomial time to randomly sample a subset $A$ of vertices of $G$ with the following properties: (i) $A$ induces a subgraph of $G$ of treewidth $\mathcal{

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e28b4032f1abc99174e82c6ff0e8e487
https://doi.org/10.1137/19m1262504

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.

On Certain Aspects of Topological Indices

Autor: Muhammad Nauman Aslam, Tanweer Ul Islam, Zeeshan Saleem Mufti, Aqsa Ameen, Ali Tabraiz

Publikováno v: Journal of Mathematics, Vol 2021 (2021)

A topological index, also known as connectivity index, is a molecular structure descriptor calculated from a molecular graph of a chemical compound which characterizes its topology. Various topological indices are categorized based on their degree, d

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

Zobrazit plný text záznamu

Planar graphs have bounded queue-number

Autor: Vida Dujmović, David R. Wood, Pat Morin, Torsten Ueckerdt, Piotr Micek, Gwenaël Joret

Publikováno v: FOCS
Annual Symposium on Foundations of Computer Science, FOCS 2019
Journal of the Association for Computing Machinery, 67 (4

We show that planar graphs have bounded queue-number, thus proving a conjecture of Heath et al. [66] from 1992. The key to the proof is a new structural tool called layered partitions , and the result that every planar graph has a vertex-partition an

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::59db40846a1d707d847f0c0bff95dff7
http://arxiv.org/abs/1904.04791

Zobrazit plný text záznamu

Tractable Parameterizations for the Minimum Linear Arrangement Problem

Autor: Hadas Shachnai, Michael R. Fellows, Danny Hermelin, Frances A. Rosamond

Publikováno v: ACM Transactions on Computation Theory. 8:1-12

The M inimum L inear A rrangement (MLA) problem involves embedding a given graph on the integer line so that the sum of the edge lengths of the embedded graph is minimized. Most layout problems are either intractable or not known to be tractable, par

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::ce4c52b3979c37c0a39ae6716c6d6b0b
https://doi.org/10.1145/2898352

Zobrazit plný text záznamu

Reconfiguration of Vertex Covers in a Graph

Autor: Hiroyuki Nooka, Xiao Zhou, Takehiro Ito

Publikováno v: IEICE Transactions on Information and Systems. :598-606

Suppose that we are given two vertex covers $C_{0}$ and $C_{t}$ of a graph G, together with an integer threshold $k\ge \max \{\left| C_0 \right| , \left| C_t \right| \}$. Then, the vertex cover reconfiguration problem is to determine whether th

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::c3f046c0351a753be34e3feb2484bc2b
https://doi.org/10.1587/transinf.2015fcp0010

Zobrazit plný text záznamu

Inflations of anti-cycles and Hadwiger’s Conjecture

Autor: Michael D. Plummer, Bjarne Toft, Anders Sune Pedersen

Publikováno v: Pedersen, A S, Plummer, M D & Toft, B 2016, ' Inflations of anti-cycles and Hadwiger's Conjecture ', Journal of Combinatorics (Somerville), vol. 7, no. 2-3, pp. 413-421 . https://doi.org/10.4310/JOC.2016.v7.n2.a10

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::fc818e7374e8f2c606e1e04dea28153f
https://doi.org/10.4310/joc.2016.v7.n2.a10

Zobrazit plný text záznamu

Hadwiger's Conjecture for the Complements of Kneser Graphs

Autor: Sanming Zhou, Guangjun Xu

Publikováno v: Journal of Graph Theory. 84:5-16

Hadwiger's conjecture asserts that every graph with chromatic number t contains a complete minor of order t. Given integers n≥2k+1≥5, the Kneser graph K(n,k) is the graph with vertices the k-subsets of an n-set such that two vertices are adjacent

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::60ba5a1269124c055f665f674c8c3103
https://doi.org/10.1002/jgt.22007

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.

Vyhledávací nástroje:

Upřesnit hledání