Zobrazeno 1 - 10
of 105
pro vyhledávání: '"Cristina Bazgan"'
Publikováno v:
Theory of Computing Systems. 66:395-415
We determine the power of the weighted sum scalarization with respect to the computation of approximations for general multiobjective minimization and maximization problems. Additionally, we introduce a new multi-factor notion of approximation that i
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e4319c3ab479cd6fd3165051c14cbfa0
https://doi.org/10.1007/s00224-021-10066-5
https://doi.org/10.1007/s00224-021-10066-5
Publikováno v:
Discrete Applied Mathematics
Discrete Applied Mathematics, Elsevier, 2020, 280, pp.23-42. ⟨10.1016/j.dam.2019.10.005⟩
Discrete Applied Mathematics, Elsevier, 2020, 280, pp.23-42. ⟨10.1016/j.dam.2019.10.005⟩
We survey the most important results regarding the domination chain parameters, including the characterisation of the domination sequence, complexity of exact and parameterised algorithms, and approximation and inapproximability ratios. We provide a
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::7666d6b86f3aeb484aa59b0821e478fc
https://doi.org/10.1016/j.dam.2019.10.005
https://doi.org/10.1016/j.dam.2019.10.005
Publikováno v:
Journal of Combinatorial Optimization. 44:1880-1899
Modifying the topology of a network to mitigate the spread of an epidemic with epidemiological constant $$\lambda $$ amounts to the NP-hard problem of finding a partial subgraph with maximum number of edges and spectral radius bounded above by $$\lam
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e42517934047f82623c052437e102bf5
https://doi.org/10.1007/s10878-020-00552-w
https://doi.org/10.1007/s10878-020-00552-w
Publikováno v:
HAL
Monte Carlo Search Algorithms for Network Traffic Engineering
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=dedup_wf_001::6b6317737e4877c24c751a4177d150a1
https://hal.archives-ouvertes.fr/hal-03595339
https://hal.archives-ouvertes.fr/hal-03595339
Publikováno v:
Theoretical Computer Science
Theoretical Computer Science, Elsevier, 2021, 873, pp.1-15. ⟨10.1016/j.tcs.2021.04.020⟩
Theoretical Computer Science, Elsevier, 2021, 873, pp.1-15. ⟨10.1016/j.tcs.2021.04.020⟩
The Min Anonymous-Edge-Rotation problem asks for an input graph G and a positive integer k to find a minimum number of edge rotations that transform G into a graph such that for each vertex there are at least k − 1 other vertices of the same degree
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::91211a4031f71f20f1047a031cf6cb1e
https://hal.archives-ouvertes.fr/hal-03505510
https://hal.archives-ouvertes.fr/hal-03505510
Publikováno v:
Bazgan, C, Chlebikova, J, Dallard, C & Pontoizeau, T 2019, ' Proportionally dense subgraph of maximum size: complexity and approximation ', Discrete Applied Mathematics, vol. 270, pp. 25-36 . https://doi.org/10.1016/j.dam.2019.07.010
Discrete Applied Mathematics
Discrete Applied Mathematics, Elsevier, 2019, 270, ⟨10.1016/j.dam.2019.07.010⟩
Discrete Applied Mathematics
Discrete Applied Mathematics, Elsevier, 2019, 270, ⟨10.1016/j.dam.2019.07.010⟩
We define a proportionally dense subgraph (PDS) as an induced subgraph of a graph with the property that each vertex in the PDS is adjacent to proportionally as many vertices in the subgraph as in the graph. We prove that the problem of finding a PDS
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::bd81dea4bd5935557108c3da594f746b
https://doi.org/10.1016/j.dam.2019.07.010
https://doi.org/10.1016/j.dam.2019.07.010
Publikováno v:
Machine Learning and Knowledge Discovery in Databases. Applied Data Science Track ISBN: 9783030865139
ECML/PKDD (4)
Machine Learning and Knowledge Discovery in Databases. Applied Data Science Track European Conference, ECML PKDD 2021, Bilbao, Spain, September 13–17, 2021, Proceedings
ECML-PKDD 2021
ECML-PKDD 2021, Sep 2021, Bilbao, Spain. pp.486-501, ⟨10.1007/978-3-030-86514-6_30⟩
ECML/PKDD (4)
Machine Learning and Knowledge Discovery in Databases. Applied Data Science Track European Conference, ECML PKDD 2021, Bilbao, Spain, September 13–17, 2021, Proceedings
ECML-PKDD 2021
ECML-PKDD 2021, Sep 2021, Bilbao, Spain. pp.486-501, ⟨10.1007/978-3-030-86514-6_30⟩
International audience; The aim of Traffic Engineering is to provide routing configurations in networks such that the used resources are minimized while maintaining a high level of quality of service (QoS). Among the optimization problems arising in
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::45260b01eba7dacf8fc0b225f79ecfbd
https://doi.org/10.1007/978-3-030-86514-6_30
https://doi.org/10.1007/978-3-030-86514-6_30
Publikováno v:
Journal of Global Optimization
Journal of Global Optimization, Springer Verlag, 2021, 80 (1), pp.87-115. ⟨10.1007/s10898-020-00951-7⟩
Journal of Global Optimization, Springer Verlag, 2021, 80 (1), pp.87-115. ⟨10.1007/s10898-020-00951-7⟩
Papadimitriou and Yannakakis (Proceedings of the 41st annual IEEE symposium on the Foundations of Computer Science (FOCS), pp 86–92, 2000) show that the polynomial-time solvability of a certain auxiliary problem determines the class of multiobjecti
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e8f55fc08801f836e80c6e119564a7c4
https://hal.archives-ouvertes.fr/hal-03118377
https://hal.archives-ouvertes.fr/hal-03118377
Publikováno v:
Information Processing Letters
Information Processing Letters, 2020, 155, ⟨10.1016/j.ipl.2019.105877⟩
Bazgan, C, Chlebikova, J & Dallard, C 2020, ' Graphs without a partition into two proportionally dense subgraphs ', Information Processing Letters, vol. 155, 105877 . https://doi.org/10.1016/j.ipl.2019.105877
Information Processing Letters, 2020, 155, ⟨10.1016/j.ipl.2019.105877⟩
Bazgan, C, Chlebikova, J & Dallard, C 2020, ' Graphs without a partition into two proportionally dense subgraphs ', Information Processing Letters, vol. 155, 105877 . https://doi.org/10.1016/j.ipl.2019.105877
A proportionally dense subgraph (PDS) is an induced subgraph of a graph such that each vertex in the PDS is adjacent to proportionally as many vertices in the subgraph as in the rest of the graph. In this paper, we study a partition of a graph into t
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3fd186c3d21f8cf21388dc792e9132c1
https://hal.archives-ouvertes.fr/hal-02448543/file/1806.10963.pdf
https://hal.archives-ouvertes.fr/hal-02448543/file/1806.10963.pdf
Publikováno v:
Theory and Practice of Computer Science-46th International Conference on Current Trends in Theory and Practice of Informatics, SOFSEM 2020
Theory and Practice of Computer Science-46th International Conference on Current Trends in Theory and Practice of Informatics, SOFSEM 2020, 2020, Limassol, Cyprus. pp.236-247, ⟨10.1007/978-3-030-38919-2_20⟩
SOFSEM 2020: Theory and Practice of Computer Science ISBN: 9783030389185
SOFSEM
Theory and Practice of Computer Science-46th International Conference on Current Trends in Theory and Practice of Informatics, SOFSEM 2020, 2020, Limassol, Cyprus. pp.236-247, ⟨10.1007/978-3-030-38919-2_20⟩
SOFSEM 2020: Theory and Practice of Computer Science ISBN: 9783030389185
SOFSEM
We introduce a parameterized dynamic version of the Red-Blue Dominating Set problem and its partial version. We prove the fixed-parameter tractability of the dynamic versions with respect to the (so called) edit-parameter while they remain \(\mathcal
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9b1de9c04b689ee609c99e238cb0ef73
https://hal.archives-ouvertes.fr/hal-03118652
https://hal.archives-ouvertes.fr/hal-03118652