Zobrazeno 1 - 10
of 45
pro vyhledávání: '"Janka Chlebíková"'
Autor:
Clément Dallard, Janka Chlebíková
Publikováno v:
Theoretical Computer Science. 895:137-150
A connected component of a vertex-coloured graph is said to be colourful if all its vertices have different colours. By extension, a graph is colourful if all its connected components are colourful. Given a vertex-coloured graph $G$ and an integer $p
Publikováno v:
Theoretical Computer Science. 960:113923
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
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
Autor:
Janka Chlebíková, Miroslav Chlebík
Publikováno v:
Chlebík, M & Chlebikova, J 2020, ' Weighted amplifiers and inapproximability results for Travelling Salesman problem ', Journal of Combinatorial Optimisation . https://doi.org/10.1007/s10878-020-00659-0
The expander graph constructions and their variants are the main tool used in gap preserving reductions to prove approximation lower bounds of combinatorial optimisation problems. In this paper we introduce the weighted amplifiers and weighted low oc
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b1f71a0a6322e65642ab242ef79319e3
https://researchportal.port.ac.uk/ws/files/23034546/Chleb_k_Chleb_kov_2020_Article_WeightedAmplifiersAndInapproxi.pdf
https://researchportal.port.ac.uk/ws/files/23034546/Chleb_k_Chleb_kov_2020_Article_WeightedAmplifiersAndInapproxi.pdf
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:
Combinatorial Optimization and Applications-14th International Conference, COCOA 2020
Combinatorial Optimization and Applications-14th International Conference, COCOA 2020, 2020, Dallas, United States. pp.242-256, ⟨10.1007/978-3-030-64843-5_17⟩
Combinatorial Optimization and Applications ISBN: 9783030648428
COCOA
Combinatorial Optimization and Applications-14th International Conference, COCOA 2020, 2020, Dallas, United States. pp.242-256, ⟨10.1007/978-3-030-64843-5_17⟩
Combinatorial Optimization and Applications ISBN: 9783030648428
COCOA
A graph is k-degree-anonymous if for each vertex there are at least \(k-1 \) other vertices of the same degree in the graph. Min Anonymous-Edge-Rotation asks for a given graph G and a positive integer k to find a minimum number of edge rotations that
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::592d8355d42c1bce88e93e3bfec2336f
https://hal.archives-ouvertes.fr/hal-03118666
https://hal.archives-ouvertes.fr/hal-03118666
Autor:
Miroslav Chlebík, Janka Chlebíková
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783030261757
COCOON
COCOON
The expander graph constructions and their variants are the main tool used in gap preserving reductions to prove approximation lower bounds of combinatorial optimisation problems. In this paper we introduce the weighted amplifiers and weighted low oc
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e8d8717bc56262a2e683e2a42d11bd70
https://doi.org/10.1007/978-3-030-26176-4_10
https://doi.org/10.1007/978-3-030-26176-4_10
Autor:
Janka Chlebíková, Clément Dallard
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783030250041
IWOCA
IWOCA
A connected component of a vertex-coloured graph is said to be colourful if all its vertices have different colours, and a graph is colourful if all its connected components are colourful. Given a vertex-coloured graph, the Colourful Components probl
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::a7a2dda3823e3dd7a7287429279ba745
https://doi.org/10.1007/978-3-030-25005-8_12
https://doi.org/10.1007/978-3-030-25005-8_12
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783030174019
CIAC
CIAC
The Dial-a-Ride problem may contain various constraints for pickup-delivery requests, such as time windows and ride time constraints. For a tour, given as a sequence of pickup and delivery stops, there exist polynomial time algorithms to find a sched
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::64a8575244c12d39ce651a231466b5b9
https://doi.org/10.1007/978-3-030-17402-6_13
https://doi.org/10.1007/978-3-030-17402-6_13