Zobrazeno 1 - 10
of 156
pro vyhledávání: '"Pinar Heggernes"'
Publikováno v:
Algorithmica. 84:3587-3602
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::7061aa75c20217a45970dc3f4cc453bd
https://doi.org/10.1007/s00453-022-00953-9
https://doi.org/10.1007/s00453-022-00953-9
Publikováno v:
Discrete Applied Mathematics
Discrete Applied Mathematics, Elsevier, 2020, 278, pp.3-11. ⟨10.1016/j.dam.2019.07.015⟩
Discrete Applied Mathematics, Elsevier, 2020, 278, pp.3-11. ⟨10.1016/j.dam.2019.07.015⟩
Enumerating objects of specified type is one of the principal tasks in algorithms. In graph algorithms an often studied task is the enumeration of vertex subsets of the input graph satisfying a certain property. We study the enumeration of all minima
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::7c57434109186a207c354fc204d7e7f7
https://hal.univ-lorraine.fr/hal-03242329
https://hal.univ-lorraine.fr/hal-03242329
Publikováno v:
LATIN 2020: Theoretical Informatics ISBN: 9783030617912
LATIN
LATIN
We determine the maximum number of edges that a chordal graph G can have if its degree, \(\Delta (G)\), and its matching number, \(\nu (G)\), are bounded. To do so, we show that for every \(d,\nu \in \mathbb {N}\), there exists a chordal graph G with
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::1aa393665f2bf1f507577d9732d0a4b3
https://doi.org/10.1007/978-3-030-61792-9_47
https://doi.org/10.1007/978-3-030-61792-9_47
Publikováno v:
European journal of combinatorics
83:103015
83:103015
Let $G = (V, E)$ be a connected graph with maximum degree $k\geq 3$ distinct from $K_{k+1}$. Given integers $s \geq 2$ and $p_1,\ldots,p_s\geq 0$, $G$ is said to be $(p_1, \dots, p_s)$-partitionable if there exists a partition of $V$ into sets~$V_1,\
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::45a7ee80cb38958dbc1abaf5e871916d
https://hdl.handle.net/11250/2740699
https://hdl.handle.net/11250/2740699
Publikováno v:
European Journal of Combinatorics. 66:191-234
One of the most famous algorithmic meta-theorems states that every graph property which can be defined in counting monadic second order logic (CMSOL) can be checked in linear time on graphs of bounded treewidth, which is known as Courcelle’s Theore
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::055315ab5b407cdf8303fa2ad5510019
https://doi.org/10.1016/j.ejc.2017.06.025
https://doi.org/10.1016/j.ejc.2017.06.025
Autor:
Pinar Heggernes, Jayme Luiz Szwarcfiter, Petr A. Golovach, Ross M. McConnell, Vinícius Fernandes dos Santos, Jeremy P. Spinrad, Nathan Lindzey
Publikováno v:
Discrete Applied Mathematics. 216:171-180
A graph G = ( V , E ) is a threshold tolerance graph if each vertex v ∈ V can be assigned a weight w v and a tolerance t v such that two vertices x , y ∈ V are adjacent if w x + w y ≥ min ( t x , t y ) . Currently, the most efficient recognitio
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::775946b4bc4e0785c44610e363c08fa7
https://doi.org/10.1016/j.dam.2015.01.034
https://doi.org/10.1016/j.dam.2015.01.034
Publikováno v:
Algorithmica
Algorithmica, Springer Verlag, 2019, 81 (7), pp.2795-2828. ⟨10.1007/s00453-019-00555-y⟩
Algorithmica, 2019, Vol.81(7), pp.2795-2828 [Peer Reviewed Journal]
Algorithmica, Springer Verlag, 2019, 81 (7), pp.2795-2828. ⟨10.1007/s00453-019-00555-y⟩
Algorithmica, 2019, Vol.81(7), pp.2795-2828 [Peer Reviewed Journal]
Deciding if a graph has a square root is a classical problem, which has been studied extensively both from graph-theoretic and algorithmic perspective. As the problem is NP-complete, substantial effort has been dedicated to determining the complexity
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2cbc2ba9111030703a0507065c29d5a2
https://hal.univ-lorraine.fr/hal-03242331
https://hal.univ-lorraine.fr/hal-03242331
Autor:
Pinar Heggernes
This book constitutes the refereed conference proceedings of the 11th International Conference on Algorithms and Complexity, CIAC 2019, held in Rome, Italy, in May 2019. The 30 full papers were carefully reviewed and selected from 95 submissions. The
Autor:
Pinar Heggernes, Faisal N. Abu-Khzam
Publikováno v:
Information Processing Letters. 116:739-743
A structural theorem about the distribution of simplicial vertices in a chordal graph.An algorithm for enumerating minimal dominating sets in a chordal graph.Upper bound on number of minimal dominating sets improved from 1.6181 n to 1.5214 n . The ma
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e86132a02b46df16b4dc36ea300441ce
https://doi.org/10.1016/j.ipl.2016.07.002
https://doi.org/10.1016/j.ipl.2016.07.002
Publikováno v:
Discrete Applied Mathematics. 205:62-72
We describe the clique-width of path powers by an exact formula, depending only on the number of vertices and the clique number. As a consequence, the clique-width of path powers can be computed in linear time. Path powers are a graph class of unboun
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::7b66540e0adac814831d6757cf967aa1
https://doi.org/10.1016/j.dam.2015.11.009
https://doi.org/10.1016/j.dam.2015.11.009