Zobrazeno 1 - 7
of 7
pro vyhledávání: '"Benjamin Bergougnoux"'
Publikováno v:
SIAM Journal on Discrete Mathematics
In this paper, we design a framework to obtain efficient algorithms for several problems with a global constraint (acyclicity or connectivity) such as Connected Dominating Set, Node Weighted Steiner Tree, Maximum Induced Tree, Longest Induced Path, a
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2f069d68313189cff8621de60dd18a67
https://doi.org/10.1137/20m1350571
https://doi.org/10.1137/20m1350571
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. 782:30-53
Given a clique-width $k$-expression of a graph $G$, we provide $2^{O(k)}\cdot n$ time algorithms for connectivity constraints on locally checkable properties such as Node-Weighted Steiner Tree, Connected Dominating Set, or Connected Vertex Cover. We
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::41d93a1e8b62b591a030d978d91a16f4
https://doi.org/10.1016/j.tcs.2019.02.030
https://doi.org/10.1016/j.tcs.2019.02.030
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
Publikováno v:
Journal of Computer and System Sciences
Journal of Computer and System Sciences, 2019, ⟨10.1016/j.jcss.2018.10.002⟩
Journal of Computer and System Sciences, Elsevier, 2019, ⟨10.1016/j.jcss.2018.10.002⟩
CoRR
CoRR, 2018, abs/1808.05017
Journal of Computer and System Sciences, 2019, ⟨10.1016/j.jcss.2018.10.002⟩
Journal of Computer and System Sciences, Elsevier, 2019, ⟨10.1016/j.jcss.2018.10.002⟩
CoRR
CoRR, 2018, abs/1808.05017
International audience; We prove that one can count in polynomial time the number of minimal transversalsof β-acyclic hypergraphs. In consequence, we can count in polynomial timethe number of minimal dominating sets of strongly chordal graphs, conti
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d2b5bf22d1e90aa890567d5c92dbf0ef
https://inria.hal.science/hal-01923090
https://inria.hal.science/hal-01923090
Autor:
Thomas Bellitto, Benjamin Bergougnoux
Publikováno v:
Graph-Theoretic Concepts in Computer Science ISBN: 9783030002558
WG
WG
A forbidden transition graph is a graph defined together with a set of permitted transitions i.e. unordered pair of adjacent edges that one may use consecutively in a walk in the graph. In this paper, we look for the smallest set of transitions neede
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ab8da6964f57eed1e2e369f1a187bcca
https://doi.org/10.1007/978-3-030-00256-5_4
https://doi.org/10.1007/978-3-030-00256-5_4
Publikováno v:
Mathematical Foundations of Computer Science (MFCS)
Mathematical Foundations of Computer Science (MFCS), Aug 2017, Aalborg, Denmark. ⟨10.4230/LIPIcs.MFCS.2017.36⟩
Algorithmica
1201–1221
Mathematical Foundations of Computer Science (MFCS), Aug 2017, Aalborg, Denmark. ⟨10.4230/LIPIcs.MFCS.2017.36⟩
Algorithmica
1201–1221
In theDirected Feedback Vertex Set (DFVS)problem, the input is a directed graphDand an integerk. The objective is to determine whether there exists a set of at mostkvertices intersecting every directed cycle ofD. DFVS was shown to be fixed-parameter
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a41b7d6191b043b4385850cec058e7d3