Zobrazeno 1 - 10
of 96
pro vyhledávání: '"Jan Arne Telle"'
Autor:
Andrzej Proskurowski, Jan Arne Telle
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol 3, Iss 4 (1999)
We introduce q-proper interval graphs as interval graphs with interval models in which no interval is properly contained in more than q other intervals, and also provide a forbidden induced subgraph characterization of this class of graphs. We initia
Externí odkaz:
https://doaj.org/article/ccbefe8f6db14837a1ba8742da4e4814
Publikováno v:
Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence.
Over the past decades in the field of machine teaching, several restrictions have been introduced to avoid ‘cheating’, such as collusion-free or non-clashing teaching. However, these restrictions forbid several teaching situations that we intuiti
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::c59828b1e6a9f8ebd6ba908b7c84627d
https://doi.org/10.24963/ijcai.2022/412
https://doi.org/10.24963/ijcai.2022/412
Publikováno v:
Discrete Applied Mathematics. 278:153-168
We initialize a series of papers deepening the understanding of algorithmic properties of the width parameter maximum induced matching width (mim-width) of graphs. In this first volume we provide the first polynomial-time algorithms on graphs of boun
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::736df3054a10d1722d536294cebabfa1
https://doi.org/10.1016/j.dam.2019.06.026
https://doi.org/10.1016/j.dam.2019.06.026
Publikováno v:
Graph-Theoretic Concepts in Computer Science ISBN: 9783031159138
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::2651ce06b763af78813c73a1f14dba10
https://doi.org/10.1007/978-3-031-15914-5_6
https://doi.org/10.1007/978-3-031-15914-5_6
Publikováno v:
Algorithmica
The two weighted graph problems Node Multiway Cut (NMC) and Subset Feedback Vertex Set (SFVS) both ask for a vertex set of minimum total weight, that for NMC disconnects a given set of terminals, and for SFVS intersects all cycles containing a vertex
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9b0f7612c8b92374bbffce8fa568108c
https://hdl.handle.net/11250/3059245
https://hdl.handle.net/11250/3059245
Publikováno v:
Theoretical Computer Science
We generalize the family of ( σ , ρ ) problems and locally checkable vertex partition problems to their distance versions, which naturally captures well-known problems such as Distance- r Dominating Set and Distance- r Independent Set . We show tha
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::995c30eb09a88de1a519712ee2bc6e3e
https://doi.org/10.1016/j.tcs.2019.09.012
https://doi.org/10.1016/j.tcs.2019.09.012
Publikováno v:
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
instname
instname
[EN] The theoretical hardness of machine teaching has usually been analyzed for a range of concept languages under several variants of the teaching dimension: the minimum number of examples that a teacher needs to figure out so that the learner ident
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a8e4f6e480e0523ee7bd644caf859d9c
https://doi.org/10.1007/s10994-019-05821-2
https://doi.org/10.1007/s10994-019-05821-2
Autor:
Jan Arne Telle, Yngve Villanger
Publikováno v:
Theoretical Computer Science. 770:62-68
We study the parameterized complexity of domination problems on sparse graphs and beyond. The nowhere dense classes of graphs have been proposed as the main model for sparseness that can be utilized algorithmically. The class of d-degenerate graphs i
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::afedb6da6c973ba90fe3d453a126bdd4
https://doi.org/10.1016/j.tcs.2018.10.030
https://doi.org/10.1016/j.tcs.2018.10.030
Autor:
Van Bang Le, Jan Arne Telle
Publikováno v:
Graph-Theoretic Concepts in Computer Science ISBN: 9783030868376
WG
WG
In a graph, a perfect matching cut is an edge cut that is a perfect matching. perfect matching cut (pmc) is the problem of deciding whether a given graph has a perfect matching cut, and is known to be \(\mathsf {NP}\)-complete. We revisit the problem
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::fc55409cdf725bc3aadc81b958599541
https://doi.org/10.1007/978-3-030-86838-3_14
https://doi.org/10.1007/978-3-030-86838-3_14
Publikováno v:
Fundamentals of Computation Theory ISBN: 9783030865924
FCT
Lecture Notes in Computer Science (LNCS)
23rd International Symposium on Fundamentals of Computation Theory (FCT 2021)
23rd International Symposium on Fundamentals of Computation Theory (FCT 2021), Sep 2021, Athens, Greece. pp.287-300, ⟨10.1007/978-3-030-86593-1_20⟩
FCT
Lecture Notes in Computer Science (LNCS)
23rd International Symposium on Fundamentals of Computation Theory (FCT 2021)
23rd International Symposium on Fundamentals of Computation Theory (FCT 2021), Sep 2021, Athens, Greece. pp.287-300, ⟨10.1007/978-3-030-86593-1_20⟩
International audience; The minimum height of vertex and edge partition trees are well-studied graph parameters known as, for instance, vertex and edge ranking number. While they are NP-hard to determine in general, linear-time algorithms exist for t
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::529e4c3af39f3415529c1b222e2af75e
https://doi.org/10.1007/978-3-030-86593-1_20
https://doi.org/10.1007/978-3-030-86593-1_20