Zobrazeno 1 - 10
of 11
pro vyhledávání: '"Pål Grønås Drange"'
Publikováno v:
Computer Science Review
The survey provides an overview of the developing area of parameterized algorithms for graph modification problems. We concentrate on edge modification problems, where the task is to change a small number of adjacencies in a graph in order to satisfy
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8dbc6aa9e77fe39bc7bc562368c01324
https://doi.org/10.1016/j.cosrev.2023.100556
https://doi.org/10.1016/j.cosrev.2023.100556
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783031066771
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::562430d1c9ef48f3165879832f244296
https://doi.org/10.1007/978-3-031-06678-8_22
https://doi.org/10.1007/978-3-031-06678-8_22
Autor:
Michał Pilipczuk, Pål Grønås Drange
Publikováno v:
Algorithmica. 80:3481-3524
We give a kernel with $O(k^7)$ vertices for Trivially Perfect Editing, the problem of adding or removing at most $k$ edges in order to make a given graph trivially perfect. This answers in affirmative an open question posed by Nastos and Gao, and by
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c37b848923b64e234fdb7a86e58abbaa
https://doi.org/10.1007/s00453-017-0401-6
https://doi.org/10.1007/s00453-017-0401-6
Publikováno v:
Algorithmica. 76:1181-1202
The Weighted Vertex Integrity (wVI) problem takes as input an $n$-vertex graph $G$, a weight function $w:V(G)\to\mathbb{N}$, and an integer $p$. The task is to decide if there exists a set $X\subseteq V(G)$ such that the weight of $X$ plus the weight
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c18d7167c7071d921b3b707f3e21fea8
https://doi.org/10.1007/s00453-016-0127-x
https://doi.org/10.1007/s00453-016-0127-x
Publikováno v:
ACM Transactions on Computation Theory. 7:1-38
Let F be a family of graphs. In the F -C ompletion problem, we are given an n -vertex graph G and an integer k as input, and asked whether at most k edges can be added to G so that the resulting graph does not contain a graph from F as an induced sub
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::d8bc889020f5a97ebb6b374cf955b9e7
https://doi.org/10.1145/2799640
https://doi.org/10.1145/2799640
Publikováno v:
LATIN 2016: Theoretical Informatics ISBN: 9783662495285
LATIN
LATIN
Recently, Aravind et al. (IPEC 2014) showed that for any finite set of connected graphs \(\mathcal {H}\), the problem \(\mathcal {H}\)-Free Edge Deletion admits a polynomial kernelization on bounded degree input graphs. We generalize this theorem by
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::5176986a14e6f6759ee8569922e76025
https://doi.org/10.1007/978-3-662-49529-2_27
https://doi.org/10.1007/978-3-662-49529-2_27
We study the computational complexity of the graph modification problems Threshold Editing and Chain Editing, adding and deleting as few edges as possible to transform the input into a threshold (or chain) graph. In this article, we show that both pr
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ad4f0d344c78a63daff4d2395f350741
Publikováno v:
Algorithms-ESA 2015 ISBN: 9783662483497
We study the computational complexity of the graph modification problems Open image in new window and Open image in new window , adding and deleting as few edges as possible to transform the input into a threshold (or chain) graph. In this article, w
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::ba27b84b92cc11eae1195aca3d975675
https://doi.org/10.1007/978-3-662-48350-3_35
https://doi.org/10.1007/978-3-662-48350-3_35
Autor:
Pål Grønås Drange, Michał Pilipczuk
Publikováno v:
Algorithms-ESA 2015 ISBN: 9783662483497
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::27dc65eb71182130b23eb3a2d50bb517
https://doi.org/10.1007/978-3-662-48350-3_36
https://doi.org/10.1007/978-3-662-48350-3_36
Publikováno v:
Algorithms and Computation ISBN: 9783319130743
ISAAC
ISAAC
The Weighted Vertex Integrity (wVI) problem takes as input an \(n\)-vertex graph \(G\), a weight function \(w:V(G)\rightarrow \mathbb {N}\), and an integer \(p\). The task is to decide if there exists a set \(X\subseteq V(G)\) such that the weight of
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::57cfacf07b845aadaf6cc59780ec2237
https://doi.org/10.1007/978-3-319-13075-0_23
https://doi.org/10.1007/978-3-319-13075-0_23