A5044841141- Advanced Graph Theory Research
- Complexity and Algorithms in Graphs
- Limits and Structures in Graph Theory
- Graph theory and applications
- Graph Labeling and Dimension Problems
- graph theory and CDMA systems
- Interconnection Networks and Systems
- Optimization and Search Problems
- Complex Network Analysis Techniques
- Computational Geometry and Mesh Generation
- Advanced Optical Network Technologies
- Topological and Geometric Data Analysis
- Game Theory and Voting Systems
- Distributed systems and fault tolerance
- Data Management and Algorithms
- Digital Image Processing Techniques
- Game Theory and Applications
- Synthesis and Properties of Aromatic Compounds
- Color Science and Applications
- Optimization and Packing Problems
- Formal Methods in Verification
- Advanced Topology and Set Theory
- Caching and Content Delivery
- Constraint Satisfaction and Optimization
- Artificial Intelligence in Games
Université de Montpellier
2015-2024
Centre National de la Recherche Scientifique
2012-2024
Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier
2015-2024
Hudson Institute
2023
Université Claude Bernard Lyon 1
2003-2005
Abstract We prove that every tournament with minimum out‐degree at least contains k disjoint 3‐cycles. This provides additional support for the conjecture by Bermond and Thomassen digraph D of vertex cycles. also , when is large enough, The linear factor 1.5 best possible as shown regular tournaments.
We consider the problem of deciding whether a given network with integer capacities has two feasible flows x and y prescribed balance vectors such that arcs carry flow in are arc-disjoint from y. This generalizes number well-studied problems as existence out-branchings Bs+, Bt+ where roots s, t may be same vertex, spanning subdigraphs D1, D2 degree sequences digraph (e.g. cycle factors), weak-2-linkage problem, partitioning etc. Hence is NP-complete general. show remains hard even for very...
Kanté and Nourine [SIAM J. Discrete Math., 30 (2016), pp. 311--326] present a polynomial time algorithm for the computation of hull number chordal graphs. We point out gap in correctness proof their graphs show that computing graph is NP-hard, which most likely rules existence algorithm.
A tournament T = (V , A) is a directed graph in which there exactly one arc between every pair of distinct vertices. Given digraph on n vertices and an integer parameter k, the Feedback Arc Set problem asks whether given has set k arcs whose removal results acyclic digraph. The restricted to tournaments known as k-Feedback Tournaments (k-FAST) problem. In this paper we obtain linear vertex kernel for k-FAST. That is, give polynomial time algorithm input instance k-FAST obtains equivalent ′...
Abstract For a given ‐partition of the vertices (di)graph , we study properties spanning bipartite subdigraph induced by those arcs/edges that have one end in each . We determine, for all pairs nonnegative integers complexity deciding whether has 2‐partition such vertex (for ) at least (out‐)neighbours prove it is ‐complete to decide digraph an out‐neighbour and in‐neighbour The problem becomes polynomially solvable if require be strongly connected. give characterisation structure instances...
As a natural variant of domination in graphs, Dankelmann et al. [Domination with exponential decay, Discrete Math. 309 (2009) 5877-5883] introduced domination, where vertices are considered to have some dominating power that decreases exponentially the distance, and dominated accumulate sufficient amount this emanating from vertices. More precisely, if $S$ is set graph $G$, then an $G$ $\sum\limits_{v\in S}\left(\frac{1}{2}\right)^{{\rm dist}_{(G,S)}(u,v)-1}\geq 1$ for every vertex $u$...
Abstract We study vertex colourings of digraphs so that no out‐neighbourhood is monochromatic and call such a colouring an out‐colouring. The problem deciding whether given digraph has out‐colouring with only two colours (called 2‐out‐colouring) ‐complete. show for every choice positive integers there exists ‐strong bipartite tournament, which needs at least in Our main results are on tournaments semicomplete digraphs. prove that, except the Paley tournament , strong minimum out‐degree three...