Search

Your search keyword '"Institut teoretické informatiky (ITI)"' showing total 15 results
Start Over Author "Institut teoretické informatiky (ITI)"
15 results on '"Institut teoretické informatiky (ITI)"'

1. Improving Performance and Accuracy of Local PCA

Author

Christian Bouville, Jaroslav Křivánek, Kadi Bouatouch, Mickaël Ribardière, Václav Gassenbauer, FRVSense (FRVSense), MEDIA ET INTERACTIONS (IRISA-D6), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA), Faculty of Electrical Engineering [Prague] (FEL CTU), Czech Technical University in Prague (CTU), Institut teoretické informatiky (ITI), Charles University [Prague] (CU), Centre Scientifique et Technique du Bâtiment (CSTB), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), and Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)

Subjects
Clustering high-dimensional data, Computer science, business.industry, Dimensionality reduction, Initialization, ACM: I.: Computing Methodologies/I.5: PATTERN RECOGNITION/I.5.3: Clustering, 020207 software engineering, 02 engineering and technology, Machine learning, computer.software_genre, Computer Graphics and Computer-Aided Design, [INFO.INFO-GR]Computer Science [cs]/Graphics [cs.GR], Computer graphics, Data set, ACM: I.: Computing Methodologies/I.3: COMPUTER GRAPHICS/I.3.7: Three-Dimensional Graphics and Realism, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Artificial intelligence, Cluster analysis, business, Focus (optics), Algorithm, computer, Data compression
Abstract

International audience; Local Principal Component Analysis (LPCA) is one of the popular techniques for dimensionality reduction and data compression of large data sets encountered in computer graphics. The LPCA algorithm is a variant of k-means clustering where the repetitive classification of high dimensional data points to their nearest cluster leads to long execution times. The focus of this paper is on improving the efficiency and accuracy of LPCA. We propose a novel SortCluster LPCA algorithm that significantly reduces the cost of the point-cluster classification stage, achieving a speed-up of up to 20. To improve the approximation accuracy, we investigate different initialization schemes for LPCA and find that the k-means++ algorithm [AV07] yields best results, however at a high computation cost. We show that similar ideas that lead to the efficiency of our SortCluster LPCA algorithm can be used to accelerate k-means++. The resulting initialization algorithm is faster than purely random seeding while producing substantially more accurate data approximation.; Analyse en composantes principales locale (LPCA) est l'une des techniques les plus répandues pour la compression des très grands volumes de données que l'on rencontre en infographie. L'algorithme LPCA est une variante du regroupement en k-means où la classification répétitive de points de haute dimensionnalité vers le groupe le plus proche conduit à de très longs temps d'exécution. Le but de cet article est de d'améliorer l'efficacité et la précision du LPCA. Nous proposons un nouvel algorithme SortCluster LPCA qui réduit significativement le coût de la classification point-cluster conduisant à une accélération dans un rapport t 20. Pour améliorer la précision de l'approximation, nous comparons différentes méthodes d'initialisation et trouvons que l'algorithme k-means++ donne les meilleurs résultats mais à un coût de calcul important. Nous montrons que des idées similaires qui améliorent l'efficacité de notre algorithme SortCluster LPCA peuvent être utilisés pour accélérer k-means++. L'algorithme d'initialisation qui en résulte est plus rapide que le simple choix aléatoire tout en produisant des approximations sensiblement meilleures.

Published
2011

2. Graphs with bounded tree-width and large odd-girth are almost bipartite

Author

Daniel Král, Jean-Sébastien Sereni, Alexandr V. Kostochka, Michael Stiebitz, Department of Mathematics [Urbana], University of Illinois at Urbana-Champaign [Urbana], University of Illinois System-University of Illinois System, Institute of Mathematics [Novosibirsk], Institute of Mathematics of Novosibirsk, Institut teoretické informatiky (ITI), Charles University [Prague] (CU), Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Institute of Mathematics - Technical University of Ilmenau, and Ilmenau University of Technology [Germany] (TU)

Subjects
Odd-girth, Circular coloring, Tree-width, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Theoretical Computer Science, Combinatorics, FOS: Mathematics, Mathematics - Combinatorics, Discrete Mathematics and Combinatorics, Chromatic scale, 05C83, 0101 mathematics, Mathematics, Discrete mathematics, 010102 general mathematics, 05C15, Graph, Treewidth, Computational Theory and Mathematics, 010201 computation theory & mathematics, Bounded function, Bipartite graph, Combinatorics (math.CO)
Abstract

International audience; We prove that for every k and every \epsilon > 0, there exists g such that every graph with tree-width at most k and odd-girth at least g has circular chromatic number at most 2 + \epsilon.

Published
2010

3. Characterisation Results for Steiner Triple Systems and Their Application to Edge-Colourings of Cubic Graphs

Author

Edita Máčajová, Jean-Sébastien Sereni, Attila Pór, Daniel Král, Institut teoretické informatiky (ITI), Charles University [Prague] (CU), Department of Computer Science - Comenius University, Comenius University in Bratislava, Department of Mathematics - Western Kentucky University (WKU), Western Kentucky University (WKU), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Department of Applied Mathematics (KAM) (KAM), and Univerzita Karlova v Praze

Subjects
Discrete mathematics, Vertex (graph theory), General Mathematics, 010102 general mathematics, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Edge (geometry), 01 natural sciences, Steiner tree problem, Combinatorics, symbols.namesake, Steiner system, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], 0103 physical sciences, symbols, Cubic graph, 05B07, 05C15, 010307 mathematical physics, Affine transformation, 0101 mathematics, MathematicsofComputing_DISCRETEMATHEMATICS, Mathematics
Abstract

It is known that a Steiner triple system is projective if and only if it does not contain the four-triple configuration C14. We find three configurations such that a Steiner triple system is affine if and only if it does not contain one of these configurations. Similarly, we characterise Hall triple systems using two forbidden configurations.Our characterisations have several interesting corollaries in the area of edge-colourings of graphs. A cubic graph G is S-edge-colourable for a Steiner triple system S if its edges can be coloured with points of S in such a way that the points assigned to three edges sharing a vertex form a triple in S. Among others, we show that all cubic graphs are S-edge-colourable for every non-projective nonaffine point-transitive Steiner triple system S.

Published
2010

4. The Last Fraction of a Fractional Conjecture

Author

Jean-Sébastien Sereni, Daniel Král, František Kardoš, Institut teoretické informatiky (ITI), Charles University [Prague] (CU), Institute of Mathematics, P.J. Safarik University, Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), and Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Discrete mathematics, Conjecture, General Mathematics, 010102 general mathematics, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, girth, Combinatorics, 05C15, total coloring, Computer Science::Discrete Mathematics, 010201 computation theory & mathematics, FOS: Mathematics, fractional coloring, Mathematics - Combinatorics, 05C15, 05C72, Combinatorics (math.CO), 0101 mathematics, Mathematics
Abstract

Reed conjectured that for every $\varepsilon>0$ and every integer $\Delta$, there exists $g$ such that the fractional total chromatic number of every graph with maximum degree $\Delta$ and girth at least $g$ is at most $\Delta+1+\varepsilon$. The conjecture was proven to be true when $\Delta=3$ or $\Delta$ is even. We settle the conjecture by proving it for the remaining cases., Comment: A typo has been corrected in the introduction (concerning the citation of the result by Ito, Kennedy and Reed)

Published
2010

5. Spatial Directional Radiance Caching

Author

Kadi Bouatouch, Václav Gassenbauer, Jaroslav Křivánek, Perception, decision and action of real and virtual humans in virtual environments and impact on real environments (BUNRAKU), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Cachan (ENS Cachan)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria), Institut teoretické informatiky (ITI), Charles University [Prague] (CU), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), and Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Cachan (ENS Cachan)-Inria Rennes – Bretagne Atlantique

Subjects
Global illumination, Computer science, business.industry, ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION, 020207 software engineering, 02 engineering and technology, Computer Graphics and Computer-Aided Design, ACM: I.: Computing Methodologies/I.3: COMPUTER GRAPHICS, [INFO.INFO-GR]Computer Science [cs]/Graphics [cs.GR], Domain (software engineering), Computer graphics (images), 0202 electrical engineering, electronic engineering, information engineering, Radiance, 020201 artificial intelligence & image processing, Computer vision, Bidirectional reflectance distribution function, Artificial intelligence, business, ComputingMilieux_MISCELLANEOUS, ComputingMethodologies_COMPUTERGRAPHICS
Abstract

We present a new approach for accelerated global illumination computation in scenes with glossy surfaces. Our algorithm combines sparse illumination computation used in the radiance caching algorithm with BRDF importance sampling. To make this approach feasible, we extend the idea of lazy illumination evaluation, used in the caching approaches, from the spatial to the directional domain. Using importance sampling allows us to apply caching not only on low-gloss but also on shiny materials with high-frequency BRDFs, for which the radiance caching algorithm breaks down.

Published
2009
Full Text
View/download PDF

6. A New Lower Bound on the Number of Perfect Matchings in Cubic Graphs

Author

Michael Stiebitz, Jean-Sébastien Sereni, Daniel Král, Institut teoretické informatiky (ITI), Charles University [Prague] (CU), Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Institute of Mathematics - Technical University of Ilmenau, and Ilmenau University of Technology [Germany] (TU)

Subjects
Discrete mathematics, perfect matching polytope, cubic graph, 05C70, General Mathematics, perfect matching, 010102 general mathematics, Strong perfect graph theorem, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Upper and lower bounds, Tutte theorem, Graph, brick and brace decomposition, Combinatorics, Computer Science::Discrete Mathematics, 010201 computation theory & mathematics, Trivially perfect graph, Cubic graph, 0101 mathematics, Mathematics
Abstract

International audience; We prove that every n-vertex cubic bridgeless graph has at least n/2 perfect matchings and give a list of all 17 such graphs that have less than n/2+2 perfect matchings.

Published
2009

7. List colorings with measurable sets

Author

Jan Hladký, Daniel Kráal, Jean-Sébastien Sereni, Michael Stiebitz, Centre for Discrete Mathematics and its Applications [Warwick] (DIMAP), University of Warwick [Coventry], Institut teoretické informatiky (ITI), Charles University [Prague] (CU), Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Institute of Mathematics - Technical University of Ilmenau, and Ilmenau University of Technology [Germany] (TU)

Subjects
list coloring, fractional chromatic number, 010102 general mathematics, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 16. Peace & justice, Hall's theorem, 01 natural sciences, 05C15, 010201 computation theory & mathematics, Discrete Mathematics and Combinatorics, measurable sets, Geometry and Topology, 0101 mathematics
Abstract

International audience; The measurable list chromatic number of a graph G is the smallest number such that if each vertex v of G is assigned a set L(v) of measure in a fixed atomless measure space, then there exist sets such that each c(v) has measure one and for every pair of adjacent vertices v and v'. We provide a simpler proof of a measurable generalization of Hall's theorem due to Hilton and Johnson [J Graph Theory 54 (2007), 179-193] and show that the measurable list chromatic number of a finite graph G is equal to its fractional chromatic number.

Published
2008

8. Limits of Order Types

Author

Goaoc, Xavier, Hubard, Alfredo, De Joannis De Verclos, Rémi, Sereni, Jean-Sébastien, Volec, Jan, Laboratoire d'Informatique Gaspard-Monge (LIGM), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), Geometric computing (GEOMETRICA), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria), Gestion et Conduite des Systèmes de Production (G-SCOP_GCSP), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), Knowledge representation, reasonning (ORPAILLEUR), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Natural Language Processing & Knowledge Discovery (LORIA - NLPKD), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Eidgenössische Technische Hochschule - Swiss Federal Institute of Technology [Zürich] (ETH Zürich), Institut teoretické informatiky (ITI), Charles University [Prague] (CU), Janos Pach, Larse Arge, ANR-11-BS02-0003,PRESAGE,méthodes PRobabilistes pour l'Éfficacité des Structures et Algorithmes GEométriques(2011), European Project: 339025,EC:FP7:ERC,ERC-2013-ADG,GUDHI(2014), Geometric Algorithms and Models Beyond the Linear and Euclidean realm (GAMBLE ), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Algorithms, Computation, Image and Geometry (LORIA - ALGO), Radboud University [Nijmegen], Centre National de la Recherche Scientifique (CNRS), Department of Mathematics and Computer Science [Emory University], Emory University [Atlanta, GA], Arge, Lars, Pach, János, Department of Algorithms, Computation, Image and Geometry (LORIA - ALGO), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Inria Nancy - Grand Est, Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Radboud university [Nijmegen], and Institut National Polytechnique de Grenoble (INPG)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut National Polytechnique de Grenoble (INPG)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)

Subjects
Sylvester’s problem, 0102 computer and information sciences, Limits of discrete structures, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], 01 natural sciences, Flag algebras, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Mathematics - Combinatorics, sylvester problem, Rigidity properties, 0101 mathematics, order types, ACM: G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.1: Combinatorics/G.2.1.1: Counting problems, Erdős-Szekeres theorem, 000 Computer science, knowledge, general works, geometric measure theory, 010102 general mathematics, ccs:G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.1: Combinatorics/G.2.1.1: Counting problems, Erdos-Szekeres, measure theory, Sylvester's problem, 010201 computation theory & mathematics, 52C10, 05D99, Computer Science, Order types, Combinatorics (math.CO), limits
Abstract

The notion of limits of dense graphs was invented, among other reasons, to attack problems in extremal graph theory. It is straightforward to define limits of order types in analogy with limits of graphs, and this paper examines how to adapt to this setting two approaches developed to study limits of dense graphs. We first consider flag algebras, which were used to open various questions on graphs to mechanical solving via semidefinite programming. We define flag algebras of order types, and use them to obtain, via the semidefinite method, new lower bounds on the density of 5- or 6-tuples in convex position in arbitrary point sets, as well as some inequalities expressing the difficulty of sampling order types uniformly. We next consider graphons, a representation of limits of dense graphs that enable their study by continuous probabilistic or analytic methods. We investigate how planar measures fare as a candidate analogue of graphons for limits of order types. We show that the map sending a measure to its associated limit is continuous and, if restricted to uniform measures on compact convex sets, a homeomorphism. We prove, however, that this map is not surjective. Finally, we examine a limit of order types similar to classical constructions in combinatorial geometry (Erdos-Szekeres, Horton...) and show that it cannot be represented by any somewhere regular measure; we analyze this example via an analogue of Sylvester's problem on the probability that k random points are in convex position., Leibniz International Proceedings in Informatics (LIPIcs), 34, ISSN:1868-8969, 31st International Symposium on Computational Geometry (SoCG 2015), ISBN:978-3-939897-83-5

Published
2015
Full Text
View/download PDF

9. Extensions of Fractional Precolorings show Discontinuous Behavior

Author

van den Heuvel, Jan, Král', Daniel, Kupec, Martin, Sereni, Jean-Sébastien, Volec, Jan, Department Mathematics [London] (LSE), London School of Economics and Political Science (LSE), Centre for Discrete Mathematics and its Applications [Warwick] (DIMAP), University of Warwick [Coventry], Institut teoretické informatiky (ITI), Charles University [Prague] (CU), Knowledge representation, reasonning (ORPAILLEUR), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Natural Language Processing & Knowledge Discovery (LORIA - NLPKD), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL), Loria & Inria Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), and Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)

Subjects
extension, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], fractional coloring, pre-coloring
Abstract

We study the following problem: given a real number k and an integer d, what is the smallest ε such that any fractional (k+ε)-precoloring of vertices at pairwise distances at least d of a fractionally k-colorable graph can be extended to a fractional (k+ε)-coloring of the whole graph? The exact values of ε were known for k∈{2}∪ [3,∞) and any d. We determine the exact values of ε for k∈ (2,3) if d=4, and k∈ [2.5,3) if d=6, and give upper bounds for k∈(2,3) if d=5,7, and k∈(2,2.5) if d=6. Surprisingly, ε viewed as a function of k is discontinuous for all those values of d.

Published
2012

10. A superlinear bound on the number of perfect matchings in cubic bridgeless graphs

Author

František Kardoš, Louis Esperet, Daniel Král, Optimisation Combinatoire (G-SCOP_OC), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), Institute of Mathematics [Kosice, Slovakia], P.J. Safarik University, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Institut teoretické informatiky (ITI), Charles University [Prague] (CU), Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)

Subjects
0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Theoretical Computer Science, Combinatorics, Indifference graph, Pathwidth, Chordal graph, Trivially perfect graph, Computer Science::Discrete Mathematics, FOS: Mathematics, Mathematics - Combinatorics, Discrete Mathematics and Combinatorics, Cograph, Graph coloring, 0101 mathematics, Mathematics, Discrete mathematics, Mathematics::Combinatorics, 010102 general mathematics, Strong perfect graph theorem, Nowhere-zero flow, 16. Peace & justice, Computational Theory and Mathematics, 010201 computation theory & mathematics, Geometry and Topology, Combinatorics (math.CO)
Abstract

Lovasz and Plummer conjectured in the 1970's that cubic bridgeless graphs have exponentially many perfect matchings. This conjecture has been verified for bipartite graphs by Voorhoeve in 1979, and for planar graphs by Chudnovsky and Seymour in 2008, but in general only linear bounds are known. In this paper, we provide the first superlinear bound in the general case., Comment: 54 pages v2: a short (missing) proof of Lemma 10 was added

Published
2012

11. Fractional colorings of cubic graphs with large girth

Author

Daniel Král, Jan Volec, František Kardoš, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Institute of Mathematics [Kosice, Slovakia], P.J. Safarik University, Institut teoretické informatiky (ITI), Charles University [Prague] (CU), Department of Applied Mathematics [Prague] (KAM), Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)

Subjects
Discrete mathematics, Mathematics::Combinatorics, Foster graph, General Mathematics, 010102 general mathematics, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, 1-planar graph, Combinatorics, Indifference graph, Pathwidth, 010201 computation theory & mathematics, Chordal graph, Computer Science::Discrete Mathematics, Triangle-free graph, FOS: Mathematics, Odd graph, Mathematics - Combinatorics, Maximal independent set, Combinatorics (math.CO), 0101 mathematics, Mathematics
Abstract

International audience; We show that every (sub)cubic n-vertex graph with sufficiently large girth has fractional chromatic number at most 2.2978, which implies that it contains an independent set of size at least 0.4352n. Our bound on the independence number is valid for random cubic graphs as well, as it improves existing lower bounds on the maximum cut in cubic graphs with large girth.

Published
2011

12. A note on antisymmetric flows in graphs

Author

Daniel Král, Tomáš Kaiser, Jean-Sébastien Sereni, Zdenk Dvořák, Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Katedra Matematiky - University of West Bohemia (KMA), University of West Bohemia [Plzeň ], Institut teoretické informatiky (ITI), Charles University [Prague] (CU), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), and European Project: 224548,EC:FP7:ICT,FP7-ICT-2007-2,AEOLUS(2008)

Subjects
Discrete mathematics, Antisymmetric relation, 010102 general mathematics, 0102 computer and information sciences, Nowhere-zero flow, Orientation (graph theory), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Theoretical Computer Science, 05C21, 05C15, Combinatorics, Flow (mathematics), Computational Theory and Mathematics, 010201 computation theory & mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology, 0101 mathematics, nowhere-zero flow, antisymmetric flow, Mathematics
Abstract

International audience; We prove that any orientation of a graph without bridges and directed 2-edge-cuts admits a (Z3^2 × Z9^3)-antisymmetric flow, which improves the bounds obtained by DeVos, Johnson and Seymour, and DeVos, Nesetril and Raspaud.

Published
2010

13. Identifying and locating-dominating codes in (random) geometric networks

Author

Tobias Müller, J.-s. Sereni, Centrum voor Wiskunde en Informatica (CWI), Centrum Wiskunde & Informatica (CWI)-Netherlands Organisation for Scientific Research, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Institut teoretické informatiky (ITI), Charles University [Prague] (CU), and Networks and Optimization

Subjects
Statistics and Probability, Dense graph, unit disk graph, 0102 computer and information sciences, 02 engineering and technology, locating-dominating code, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], random geometric graph, 01 natural sciences, Theoretical Computer Science, Combinatorics, Indifference graph, Pathwidth, identifying code, Chordal graph, Random regular graph, 0202 electrical engineering, electronic engineering, information engineering, Cograph, Mathematics, Random graph, Discrete mathematics, Applied Mathematics, 020206 networking & telecommunications, 1-planar graph, Computational Theory and Mathematics, 010201 computation theory & mathematics, ComputingMethodologies_DOCUMENTANDTEXTPROCESSING
Abstract

We model a problem about networks built from wireless devices using identifying and locating–dominating codes in unit disk graphs. It is known that minimizing the size of an identifying code is -complete even for bipartite graphs. First, we improve this result by showing that the problem remains -complete for bipartite planar unit disk graphs. Then, we address the question of the existence of an identifying code for random unit disk graphs. We derive the probability that there exists an identifying code as a function of the radius of the disks, and we find that for all interesting ranges of r this probability is bounded away from one. The results obtained are in sharp contrast to those concerning random graphs in the Erdős–Rényi model. Another well-studied class of codes is that of locating–dominating codes, which are less demanding than identifying codes. A locating–dominating code always exists, but minimizing its size is still -complete in general. We extend this result to our setting by showing that this question remains -complete for arbitrary planar unit disk graphs. Finally, we study the minimum size of such a code in random unit disk graphs, and we prove that with probability tending to one, it is of size (n/r)2/3+o(1) if r ≤ /2−ϵ is chosen such that nr2 → ∞, and of size n1+o(1) if nr2 ≪ lnn.

Published
2009

14. Long cycles in fullerene graphs

Author

Ondřej Pangrác, Daniel Král, Jean-Sébastien Sereni, Riste Škrekovski, Institut teoretické informatiky (ITI), Charles University [Prague] (CU), Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Oddelek za Matematiko, and University of Ljubljana

Subjects
0303 health sciences, Fullerene, 05C38, 92E10, Fullerene graph, Applied Mathematics, 0102 computer and information sciences, General Chemistry, 01 natural sciences, Cubic planar graph, Graph, Combinatorics, [CHIM.THEO]Chemical Sciences/Theoretical and/or physical chemistry, 03 medical and health sciences, 010201 computation theory & mathematics, Long cycle, Hamilton cycle, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Physics::Atomic and Molecular Clusters, Mathematics - Combinatorics, Combinatorics (math.CO), 030304 developmental biology, Mathematics
Abstract

It is conjectured that every fullerene graph is hamiltonian. Jendrol' and Owens proved [J. Math. Chem. 18 (1995), pp. 83--90] that every fullerene graph on n vertices has a cycle of length at least 4n/5. In this paper, we improve this bound to 5n/6-2/3., 12 pages, 10 figures

Published
2008

15. Facial colorings using Hall’s Theorem

Author

Frédéric Havet, Daniel Král, Riste Škrekovski, Jean-Sébastien Sereni, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Institut teoretické informatiky (ITI), Charles University [Prague] (CU), Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Faculty of Mathematics and Physics [Ljubljana] (FMF), University of Ljubljana, Égide eco-net project 16305SB, European Project: 224548,EC:FP7:ICT,FP7-ICT-2007-2,AEOLUS(2008), Université Nice Sophia Antipolis (... - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS)

Subjects
Discrete mathematics, 010102 general mathematics, 0102 computer and information sciences, Complete coloring, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Theoretical Computer Science, Brooks' theorem, Combinatorics, Greedy coloring, Edge coloring, 05C15, Computational Theory and Mathematics, 010201 computation theory & mathematics, Graph power, Computer Science::Computer Vision and Pattern Recognition, Discrete Mathematics and Combinatorics, Geometry and Topology, Graph coloring, 0101 mathematics, Fractional coloring, Mathematics, List coloring
Abstract

International audience; A vertex coloring of a plane graph is ℓ-facial if every two distinct vertices joined by a facial walk of length at most ℓ receive distinct colors. It has been conjectured that every plane graph has an ℓ-facial coloring with at most 3ℓ+1 colors. We improve the currently best known bound and show that every plane graph has an ℓ-facial coloring with at most 7ℓ/2+6 colors. Our proof uses the standard discharging technique, however, in the reduction part we have successfully applied Hall's Theorem, which seems to be quite an unusual approach in this area.

Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results