Zobrazeno 1 - 10
of 205
pro vyhledávání: '"Daniël Paulusma"'
Publikováno v:
Theoretical computer science, 2022, Vol.936, pp.33-42 [Peer Reviewed Journal]
For a connected graph $G=(V,E)$, a matching $M\subseteq E$ is a matching cut of $G$ if $G-M$ is disconnected. It is known that for an integer $d$, the corresponding decision problem Matching Cut is polynomial-time solvable for graphs of diameter at m
Publikováno v:
Journal of computer and system sciences, 2022, Vol.128, pp.71-85 [Peer Reviewed Journal]
For the Odd Cycle Transversal problem, the task is to find a small set S of vertices in a graph that intersects every cycle of odd length. The Subset Odd Cycle Transversal problem requires S to intersect only those odd cycles that include a vertex of
Publikováno v:
Theoretical Computer Science, 2022, Vol.902, pp.76-92 [Peer Reviewed Journal]
We study the computational complexity of two well-known graph transversal problems, namely Subset Feedback Vertex Set and Subset Odd Cycle Transversal, by restricting the input to $H$-free graphs, that is, to graphs that do not contain some fixed gra
Publikováno v:
Algorithmica, 2023 [Peer Reviewed Journal]
Paths $$P^1,\ldots ,P^k$$ P 1 , … , P k in a graph $$G=(V,E)$$ G = ( V , E ) are mutually induced if any two distinct $$P^i$$ P i and $$P^j$$ P j have neither common vertices nor adjacent vertices. The Induced Disjoint Paths problem is to decide if
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6fd6b9ecb7e4b9dd3afda85d44e2946a
https://hdl.handle.net/1874/424823
https://hdl.handle.net/1874/424823
Autor:
Daniël Paulusma, Jana Novotná, Tomáš Masařík, Veronika Slívová, Josef Malík, Tereza Klimošová
Publikováno v:
Hsu, Wen-Lian & Lee, Der-Tsai & Liao, Chung-Shou (Eds.). (2018). 29th International Symposium on Algorithms and Computation (ISAAC 2018). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, pp. 5:1-5:13, Leibniz international proceedings in informatics(123)
Algorithmica, 2020, Vol.82(7), pp.1833-1858 [Peer Reviewed Journal]
Algorithmica, 2020, Vol.82(7), pp.1833-1858 [Peer Reviewed Journal]
The $k$-Colouring problem is to decide if the vertices of a graph can be coloured with at most $k$ colours for a fixed integer $k$ such that no two adjacent vertices are coloured alike. If each vertex u must be assigned a colour from a prescribed lis
Publikováno v:
European Symposium on Algorithms
ACM Transaction on Computational Logic
ACM Transactions on Computational Logic, 2022, Vol.23(3), pp.1-22 [Peer Reviewed Journal]
The 29th Annual European Symposium on Algorithms (ESA 2021), Lisbon / Online, 6-8 Sept 2021 [Conference proceedings]
ACM Transaction on Computational Logic
ACM Transactions on Computational Logic, 2022, Vol.23(3), pp.1-22 [Peer Reviewed Journal]
The 29th Annual European Symposium on Algorithms (ESA 2021), Lisbon / Online, 6-8 Sept 2021 [Conference proceedings]
We give a complexity dichotomy for the Quantified Constraint Satisfaction Problem QCSP(H) when H is a reflexive tournament. It is well-known that reflexive tournaments can be split into a sequence of strongly connected components H_1,...,H_n so that
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8d6b454af0870d708b68924b11276149
https://ora.ox.ac.uk/objects/uuid:b99ea8d1-d391-4314-b0ec-5090bd33b5ee
https://ora.ox.ac.uk/objects/uuid:b99ea8d1-d391-4314-b0ec-5090bd33b5ee
Publikováno v:
Bekos, M.A. & Kaufmann, M. (Eds.). Graph-Theoretic Concepts in Computer Science. WG 2022. : Springer, pp. 412-424, Lecture Notes in Computer Science, Vol.13453
Graph-Theoretic Concepts in Computer Science ISBN: 9783031159138
Graph-Theoretic Concepts in Computer Science ISBN: 9783031159138
In the FEEDBACK VERTEX SET problem, we aim to find a small set S of vertices in a graph intersecting every cycle. The SUBSET FEEDBACK VERTEX SET problem requires S to intersect only those cycles that include a vertex of some specified set T. We also
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::30ed3a1e735620a8ebf3ff8bbc6df436
http://dro.dur.ac.uk/37189/
http://dro.dur.ac.uk/37189/
Publikováno v:
WALCOM: Algorithms and Computation ISBN: 9783030967307
Mutzel, Petra & Rahman, Md. Saidur & Slamin, (Eds.). WALCOM: Algorithms and Computation: 16th International Conference and Workshops, WALCOM 2022, Jember, Indonesia, March 24-26, 2022, Proceedings. : Springer, pp. 175-186, Lecture Notes in Computer Science, Vol.13174
Mutzel, Petra & Rahman, Md. Saidur & Slamin, (Eds.). WALCOM: Algorithms and Computation: 16th International Conference and Workshops, WALCOM 2022, Jember, Indonesia, March 24-26, 2022, Proceedings. : Springer, pp. 175-186, Lecture Notes in Computer Science, Vol.13174
The L(p, q)-Edge-Labelling problem is the edge variant of the well-known L(p, q)-Labelling problem. It is equivalent to the L(p, q)-Labelling problem itself if we restrict the input of the latter problem to line graphs. So far, the complexity of L(p,
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::73d7ace6fb776ab895a425855465765c
https://doi.org/10.1007/978-3-030-96731-4_15
https://doi.org/10.1007/978-3-030-96731-4_15
Publikováno v:
Bekos, M.A. & Kaufmann, M. (Eds.). Graph-Theoretic Concepts in Computer Science. WG 2022. : Springer, pp. 114-128, Lecture Notes in Computer Science, Vol.13453
Graph-Theoretic Concepts in Computer Science ISBN: 9783031159138
Graph-Theoretic Concepts in Computer Science ISBN: 9783031159138
A homomorphism ϕ from a guest graph G to a host graph H is locally bijective, injective or surjective if for every u∈V(G), the restriction of ϕ to the neighbourhood of u is bijective, injective or surjective, respectively. The corresponding decis
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3f5a00a23d9c356cdb2674b72f08fcfe
http://dro.dur.ac.uk/37188/
http://dro.dur.ac.uk/37188/
Autor:
Konrad K. Dabrowski, François Dross, Jisu Jeong, Mamadou M. Kanté, O-joung Kwon, Sang-il Oum, Daniël Paulusma
Publikováno v:
Scopus-Elsevier
SIAM journal on discrete mathematics, 2021, Vol.35(4), pp.2922-2945 [Peer Reviewed Journal]
SIAM Journal on Discrete Mathematics
SIAM Journal on Discrete Mathematics, 2021, 35 (4), pp.2922-2945. ⟨10.1137/21M1402339⟩
SIAM journal on discrete mathematics, 2021, Vol.35(4), pp.2922-2945 [Peer Reviewed Journal]
SIAM Journal on Discrete Mathematics
SIAM Journal on Discrete Mathematics, 2021, 35 (4), pp.2922-2945. ⟨10.1137/21M1402339⟩
Tree-width and its linear variant path-width play a central role for the graph minor relation. In particular, Robertson and Seymour (1983) proved that for every tree~$T$, the class of graphs that do not contain $T$ as a minor has bounded path-width.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::15133ded7c08377859a9c00d2d90405d
https://eprints.whiterose.ac.uk/177573/1/treepivot.pdf
https://eprints.whiterose.ac.uk/177573/1/treepivot.pdf