Search

Your search keyword '"Thomas Bellitto"' showing total 37 results
Start Over Author "Thomas Bellitto"
37 results on '"Thomas Bellitto"'

1. Homomorphically Full Oriented Graphs

Author

Thomas Bellitto, Christopher Duffy, and Gary MacGillivray

Subjects
computer science - discrete mathematics, mathematics - combinatorics, 05c60, 05c20, 68q17, Mathematics, QA1-939
Abstract

Homomorphically full graphs are those for which every homomorphic image is isomorphic to a subgraph. We extend the definition of homomorphically full to oriented graphs in two different ways. For the first of these, we show that homomorphically full oriented graphs arise as quasi-transitive orientations of homomorphically full graphs. This in turn yields an efficient recognition and construction algorithms for these homomorphically full oriented graphs. For the second one, we show that the related recognition problem is GI-hard, and that the problem of deciding if a graph admits a homomorphically full orientation is NP-complete. In doing so we show the problem of deciding if two given oriented cliques are isomorphic is GI-complete.

Published
2023
Full Text
View/download PDF

2. On the density of sets of the Euclidean plane avoiding distance 1

Author

Thomas Bellitto, Arnaud Pêcher, and Antoine Sédillot

Subjects
mathematics - metric geometry, computer science - discrete mathematics, mathematics - combinatorics, Mathematics, QA1-939
Abstract

A subset $A \subset \mathbb R^2$ is said to avoid distance $1$ if: $\forall x,y \in A, \left\| x-y \right\|_2 \neq 1.$ In this paper we study the number $m_1(\mathbb R^2)$ which is the supremum of the upper densities of measurable sets avoiding distance 1 in the Euclidean plane. Intuitively, $m_1(\mathbb R^2)$ represents the highest proportion of the plane that can be filled by a set avoiding distance 1. This parameter is related to the fractional chromatic number $\chi_f(\mathbb R^2)$ of the plane. We establish that $m_1(\mathbb R^2) \leq 0.25647$ and $\chi_f(\mathbb R^2) \geq 3.8991$.

Published
2021
Full Text
View/download PDF

3. Complexity of locally-injective homomorphisms to tournaments

Author

Stefan Bard, Thomas Bellitto, Christopher Duffy, Gary MacGillivray, and Feiran Yang

Subjects
computer science - discrete mathematics, mathematics - combinatorics, 05c15, Mathematics, QA1-939
Abstract

For oriented graphs $G$ and $H$, a homomorphism $f: G \rightarrow H$ is locally-injective if, for every $v \in V(G)$, it is injective when restricted to some combination of the in-neighbourhood and out-neighbourhood of $v$. Two of the possible definitions of local-injectivity are examined. In each case it is shown that the associated homomorphism problem is NP-complete when $H$ is a reflexive tournament on three or more vertices with a loop at every vertex, and solvable in polynomial time when $H$ is a reflexive tournament on two or fewer vertices.

Published
2018
Full Text
View/download PDF

27. Restless Exploration of Periodic Temporal Graphs

Author

Thomas Bellitto and Cyril Conchon-Kerjan and Bruno Escoffier, Bellitto, Thomas, Conchon-Kerjan, Cyril, Escoffier, Bruno, Thomas Bellitto and Cyril Conchon-Kerjan and Bruno Escoffier, Bellitto, Thomas, Conchon-Kerjan, Cyril, and Escoffier, Bruno

Abstract

A temporal graph is a sequence of graphs, indexed by discrete time steps, with a fixed vertex set but with an edge set that is able to change over time. In the temporal graph exploration problem, an agent wants to visit all the vertices of a given temporal graph. In the classical model, at each time step the agent can either stay where they are, or move along one edge. In this work we add a constraint called restlessness that forces the agent to move along one edge at each time step. We mainly focus on (infinite) periodical temporal graphs. We show that if the period is 2 one can decide in polynomial time whether exploring the whole graph is possible or not, while this problem turns out to be NP-hard for any period p ≥ 3. We also show some time bounds on the explorations of such graphs when the exploration is possible.

Published
2023
Full Text
View/download PDF

33. The Complexity of Connectivity Problems in Forbidden-Transition Graphs And Edge-Colored Graphs

Author

Thomas Bellitto and Shaohua Li and Karolina Okrasa and Marcin Pilipczuk and Manuel Sorge, Bellitto, Thomas, Li, Shaohua, Okrasa, Karolina, Pilipczuk, Marcin, Sorge, Manuel, Thomas Bellitto and Shaohua Li and Karolina Okrasa and Marcin Pilipczuk and Manuel Sorge, Bellitto, Thomas, Li, Shaohua, Okrasa, Karolina, Pilipczuk, Marcin, and Sorge, Manuel

Abstract

The notion of forbidden-transition graphs allows for a robust generalization of walks in graphs. In a forbidden-transition graph, every pair of edges incident to a common vertex is permitted or forbidden; a walk is compatible if all pairs of consecutive edges on the walk are permitted. Forbidden-transition graphs and related models have found applications in a variety of fields, such as routing in optical telecommunication networks, road networks, and bio-informatics. We initiate the study of fundamental connectivity problems from the point of view of parameterized complexity, including an in-depth study of tractability with regards to various graph-width parameters. Among several results, we prove that finding a simple compatible path between given endpoints in a forbidden-transition graph is W[1]-hard when parameterized by the vertex-deletion distance to a linear forest (so it is also hard when parameterized by pathwidth or treewidth). On the other hand, we show an algebraic trick that yields tractability when parameterized by treewidth of finding a properly colored Hamiltonian cycle in an edge-colored graph; properly colored walks in edge-colored graphs is one of the most studied special cases of compatible walks in forbidden-transition graphs.

Published
2020
Full Text
View/download PDF

34. Proper-walk connection number of graphs

Author

Jørgen Bang-Jensen, Anders Yeo, and Thomas Bellitto

Subjects
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Existential quantification, Data_MISCELLANEOUS, connecting edge-colouring, 0102 computer and information sciences, Characterization (mathematics), 01 natural sciences, Combinatorics, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, 0101 mathematics, Time complexity, Connectivity, Mathematics, 010102 general mathematics, proper connection by walks, Graph, 010201 computation theory & mathematics, connected graph, Connection number, strongly connected digraph, Geometry and Topology, Combinatorics (math.CO), Computer Science - Discrete Mathematics, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

This paper studies the problem of proper-walk connection number: given an undirected connected graph, our aim is to colour its edges with as few colours as possible so that there exists a properly coloured walk between every pair of vertices of the graph i.e. a walk that does not use consecutively two edges of the same colour. The problem was already solved on several classes of graphs but still open in the general case. We establish that the problem can always be solved in polynomial time in the size of the graph and we provide a characterization of the graphs that can be properly connected with $k$ colours for every possible value of $k$., Comment: 25 pages, 9 figures

Published
2019
Full Text
View/download PDF

35. On the density of sets avoiding parallelohedron distance 1

Author

Arnaud Pêcher, Philippe Moustrou, Christine Bachoc, Thomas Bellitto, Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Reformulations based algorithms for Combinatorial Optimization (Realopt), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), This study has been carried out with financial support from the French State, managed by the French National Research Agency (ANR) in the frame of the 'Investments for the future' Programme IdEx Bordeaux - CPU (ANR-10-IDEX-03-02), ANR-10-IDEX-0003,IDEX BORDEAUX,Initiative d'excellence de l'Université de Bordeaux(2010), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, and IdEx Bordeaux - CPU

Subjects
050101 languages & linguistics, Parallelohedron, [SHS.INFO]Humanities and Social Sciences/Library and information sciences, Dimension (graph theory), 1991Mathematics Subject Classification.52C10, 52B11, 11H06, Polytope, 02 engineering and technology, Space (mathematics), Theoretical Computer Science, Combinatorics, Mathematics - Metric Geometry, TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, 52C10, 52B11, 11H06, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], 0202 electrical engineering, electronic engineering, information engineering, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, 0501 psychology and cognitive sciences, [MATH.MATH-MG]Mathematics [math]/Metric Geometry [math.MG], Mathematics, chromatic numbers, 05 social sciences, Chromatic number, Metric Geometry (math.MG), Distance graphs, Lattices, Euclidean distance, Computational Theory and Mathematics, Parallelohedra, 020201 artificial intelligence & image processing, Geometry and Topology, Combinatorics (math.CO), Voronoi diagram
Abstract

The maximal density of a measurable subset of $${{\mathbb {R}}}^n$$ avoiding Euclidean distance 1 is unknown except in the trivial case of dimension 1. In this paper, we consider the case of a distance associated to a polytope that tiles space, where it is likely that the sets avoiding distance 1 are of maximal density $$2^{-n}$$ , as conjectured by Bachoc and Robins. We prove that this is true for $$n=2$$ , and for the Voronoi regions of the lattices $$A_n$$ , $$n\ge 2$$ .

Published
2017
Full Text
View/download PDF

36. Separating codes and traffic monitoring

Author

Thomas Bellitto, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Reformulations based algorithms for Combinatorial Optimization (Realopt), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Institut de Mathématiques de Bordeaux (IMB), and Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest

Subjects
Theoretical computer science, General Computer Science, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, Directed graph, Monitoring problem, 01 natural sciences, Theoretical Computer Science, Philosophy of language, 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, [INFO]Computer Science [cs], Integer programming, Algorithm, Mathematics
Abstract

International audience; This paper studies the problem of traffic monitoring which consists of differentiating a set of walks on a directed graph by placing sensors on as few arcs as possible. The problem of characterising a set of individuals by testing as few attributes as possible is already well-known, but traffic monitoring presents new challenges that the previous models of separation fall short from modelling such as taking into account the multiplicity and order of the arcs in a walk. We introduce a new and stronger model of separation based on languages that generalises the traffic monitoring problem. We study three subproblems with practical applications and develop methods to solve them by combining integer linear programming, separating codes and language theory.

Published
2017
Full Text
View/download PDF

37. Next Generation Cluster Editing

Author

Alexander Schönhuth, Thomas Bellitto, Tobias Marschall, Gunnar W. Klau, and Evolutionary Intelligence

Subjects
Structural variation, FOS: Computer and information sciences, Theoretical computer science, Optimization problem, Computer science, Computer Science - Data Structures and Algorithms, Cluster (physics), Graph theory, Statistical model, Data Structures and Algorithms (cs.DS), Genome, Graph, Statistical hypothesis testing
Abstract

Genomic structural variations play key roles in genetic diversity and disease. Despite recent advances in structural variation discovery, many variants are yet to be discovered. Midsize insertions and deletions pose particularly involved algorithmic challenges. The recent CLEVER algorithm addressed these challenges with a statistical model on cliques in a graph whose nodes are read alignments and whose edges arise from a statistical test on length and overlap of read alignments. However, the resulting read alignment clusters tend to be too small and are heavily overlapping, which leads to losses in recall performance rates. Here we present a model based on weighted cluster editing, which alleviates these issues: clusters are provably non-overlapping and tend to be larger. In order to render the inherent optimization problem tractable on all read alignments of a genome, we present a novel, principled heuristic, which runs in time linear in the length of the genome. The heuristic is based on an exact polynomial-time algorithm for weighted cluster editing in one-dimensional point graphs. We demonstrate that the new model improves recall rates achieved by CLEVER.

Published
2015

Catalog

Books, media, physical & digital resources
See catalog results