The Experts below are selected from a list of 2787 Experts worldwide ranked by ideXlab platform
Andreas Björklund - One of the best experts on this subject based on the ideXlab platform.
-
an asymptotically fast polynomial space algorithm for hamiltonicity detection in sparse directed graphs
Symposium on Theoretical Aspects of Computer Science, 2021Co-Authors: Andreas BjörklundAbstract:We present a polynomial space Monte Carlo algorithm that given a directed graph on n vertices and average Outdegree δ, detects if the graph has a Hamiltonian cycle in 2^{n-Ω(n/δ)} time. This asymptotic scaling of the savings in the running time matches the fastest known exponential space algorithm by Bjorklund and Williams ICALP 2019. By comparison, the previously best polynomial space algorithm by Kowalik and Majewski IPEC 2020 guarantees a 2^{n-Ω(n/(2^δ))} time bound. Our algorithm combines for the first time the idea of obtaining a fingerprint of the presence of a Hamiltonian cycle through an inclusion-exclusion summation over the Laplacian of the graph from Bjorklund, Kaski, and Koutis ICALP 2017, with the idea of sieving for the non-zero terms in an inclusion-exclusion summation by listing solutions to systems of linear equations over ℤ₂ from Bjorklund and Husfeldt FOCS 2013.
-
An Asymptotically Fast Polynomial Space Algorithm for Hamiltonicity Detection in Sparse Directed Graphs.
arXiv: Data Structures and Algorithms, 2020Co-Authors: Andreas BjörklundAbstract:We present a polynomial space Monte Carlo algorithm that given a directed graph on $n$ vertices and average Outdegree $\delta$, detects if the graph has a Hamiltonian cycle in $2^{n-\Omega(\frac{n}{\delta})}$ time. This asymptotic scaling of the savings in the running time matches the fastest known exponential space algorithm by Bjorklund and Williams ICALP 2019. By comparison, the previously best polynomial space algorithm by Kowalik and Majewski IPEC 2020 guarantees a $2^{n-\Omega(\frac{n}{2^\delta})}$ time bound. Our algorithm combines for the first time the idea of obtaining a fingerprint of the presence of a Hamiltonian cycle through an inclusion--exclusion summation over the Laplacian of the graph from Bjorklund, Kaski, and Koutis ICALP 2017, with the idea of sieving for the non-zero terms in an inclusion--exclusion summation by listing solutions to systems of linear equations over $\mathbb{Z}_2$ from Bjorklund and Husfeldt FOCS 2013.
Lochet William - One of the best experts on this subject based on the ideXlab platform.
-
Immersion of transitive tournaments in digraphs with large minimum Outdegree
'Elsevier BV', 2019Co-Authors: Lochet WilliamAbstract:International audienceWe prove the existence of a function $h(k)$ such that every simple digraph with minimum Outdegree greater than $h(k)$ contains an immersion of the transitive tournament on k vertices. This solves a conjecture of Devos, McDonald, Mohar and Scheide
-
Sous-structures dans les graphes dirigés
HAL CCSD, 2018Co-Authors: Lochet WilliamAbstract:The main purpose of the thesis was to exhibit sufficient conditions on digraphs to find subdivisions of complex structures. While this type of question is pretty well understood in the case of (undirected) graphs, few things are known for the case of directed graphs (also called digraphs). The most notorious conjecture is probably the one due to Mader in 1985. He asked if there exists a function f such that every digraph with minimum Outdegree at least f(k) contains a subdivision of the transitive tournament on k vertices. The conjecture is still wide open as even the existence of f(5) remains open. This thesis presents some weakening of this conjecture. Among other results, we prove that digraphs with large minimum Outdegree contain large in-arborescences. We also prove that digraphs with large minimum Outdegree contain large transitive tournaments as immersions, which was conjectured by DeVos et al. in 2011. Changing the parameter, we also prove that large chromatic number can force subdivision of cycles and other structures in strongly connected digraphs. This thesis also presents the proof of the Erd\H{o}s-Sands-Sauer-Woodrow conjecture that states that the domination number of tournaments whose arc set can be partitioned into k transitive digraphs only depends on k. The conjecture, asked in 1982, was still open for k=3. Finally this thesis presents proofs for two results, one about orientation of hypergraphs and the other about AVD colouring using the recently developed probabilistic technique of entropy compression.Le but principal de cette thèse est de présenter des conditions suffisantes pour garantir l'existence de subdivisions dans les graphes dirigés. Bien que ce genre de questions soit assez bien maitrisé dans le cas des graphes non orientés, très peu de résultats sont connus sur le sujet des graphes dirigés. La conjecture la plus célèbre du domaine est sans doute celle attribuée à Mader en 1985 qui dit qu'il existe une fonction f tel que tout graphe dirigé de degré sortant minimal supérieur à f(k) contient le tournoi transitif sur k sommets comme subdivision. Cette question est toujours ouverte pour k=5. Cette thèse présente quelques résultats intermédiaires tendant vers cette conjecture. Il y est d'abords question de montrer l'existence de subdivisions de graphes dirigés autre que les tournois, en particulier les arborescences entrantes. Il y a aussi la preuve que les graphes dirigés de grand degré sortant contiennent des immersions de grand tournois transitifs, question qui avait été posée en 2011 par DeVos et al. En regardant un autre paramètre, on montre aussi qu'un grand nombre chromatique permet de forcer des subdivisions de certains cycles orientés, ainsi que d'autre structures, pour des graphes dirigés fortement connexes. Cette thèse présente également la preuve de la conjecture de Erd\H{o}s-Sands-Sauer-Woodrow qui dit que les tournois dont les arcs peuvent être partitionnés en k graphes dirigés transitifs peuvent être dominé par un ensemble de sommet dont la taille dépend uniquement de k. Pour finir, cette thèse présente la preuve de deux résultats, un sur l'orientation des hypergraphes et l'autre sur la coloration AVD,utilisant la technique de compression d'entropie
-
Substructures in digraphs
2018Co-Authors: Lochet WilliamAbstract:Le but principal de cette thèse est de présenter des conditions suffisantes pour garantir l'existence de subdivisions dans les graphes dirigés. Bien que ce genre de questions soit assez bien maitrisé dans le cas des graphes non orientés, très peu de résultats sont connus sur le sujet des graphes dirigés. La conjecture la plus célèbre du domaine est sans doute celle attribuée à Mader en 1985 qui dit qu'il existe une fonction f tel que tout graphe dirigé de degré sortant minimal supérieur à f(k) contient le tournoi transitif sur k sommets comme subdivision. Cette question est toujours ouverte pour k=5. Cette thèse présente quelques résultats intermédiaires tendant vers cette conjecture. Il y est d'abords question de montrer l'existence de subdivisions de graphes dirigés autre que les tournois, en particulier les arborescences entrantes. Il y a aussi la preuve que les graphes dirigés de grand degré sortant contiennent des immersions de grand tournois transitifs, question qui avait été posée en 2011 par DeVos et al. En regardant un autre paramètre, on montre aussi qu'un grand nombre chromatique permet de forcer des subdivisions de certains cycles orientés, ainsi que d'autre structures, pour des graphes dirigés fortement connexes. Cette thèse présente également la preuve de la conjecture de Erd\H{o}s-Sands-Sauer-Woodrow qui dit que les tournois dont les arcs peuvent être partitionnés en k graphes dirigés transitifs peuvent être dominé par un ensemble de sommet dont la taille dépend uniquement de k. Pour finir, cette thèse présente la preuve de deux résultats, un sur l'orientation des hypergraphes et l'autre sur la coloration AVD,utilisant la technique de compression d'entropie.The main purpose of the thesis was to exhibit sufficient conditions on digraphs to find subdivisions of complex structures. While this type of question is pretty well understood in the case of (undirected) graphs, few things are known for the case of directed graphs (also called digraphs). The most notorious conjecture is probably the one due to Mader in 1985. He asked if there exists a function f such that every digraph with minimum Outdegree at least f(k) contains a subdivision of the transitive tournament on k vertices. The conjecture is still wide open as even the existence of f(5) remains open. This thesis presents some weakening of this conjecture. Among other results, we prove that digraphs with large minimum Outdegree contain large in-arborescences. We also prove that digraphs with large minimum Outdegree contain large transitive tournaments as immersions, which was conjectured by DeVos et al. in 2011. Changing the parameter, we also prove that large chromatic number can force subdivision of cycles and other structures in strongly connected digraphs. This thesis also presents the proof of the Erd\H{o}s-Sands-Sauer-Woodrow conjecture that states that the domination number of tournaments whose arc set can be partitioned into k transitive digraphs only depends on k. The conjecture, asked in 1982, was still open for k=3. Finally this thesis presents proofs for two results, one about orientation of hypergraphs and the other about AVD colouring using the recently developed probabilistic technique of entropy compression
Carlos Jiménez - One of the best experts on this subject based on the ideXlab platform.
-
CCDF second-order weighted Outdegree input-output matrices 1975–1993.
2018Co-Authors: Pedro P. Romero, Ricardo López, Carlos JiménezAbstract:(A) Matrix 1993, 34 economic sectors. (B) Matrix 1990, 34 economic sectors. (C) Matrix 1985, 34 economic sectors. (D) Matrix 1980, 34 economic sectors. (E) Matrix 1975, 34 economic sectors. Log-log plots of the empirical counter-cumulative density functions of the weighted second-order Outdegree.
-
CCDF first-order weighted Outdegree input-output matrices 1975–1993.
2018Co-Authors: Pedro P. Romero, Ricardo López, Carlos JiménezAbstract:(A) Matrix 1993, 34 economic sectors. (B) Matrix 1990, 34 economic sectors. (C) Matrix 1985, 34 economic sectors. (D) Matrix 1980, 34 economic sectors. (E) Matrix 1975, 34 economic sectors. Log-log plots of the empirical counter-cumulative density functions (CCDF) of the weighted first-order Outdegree.
-
CCDF second-order weighted Outdegree input-output matrices 1995–2012.
2018Co-Authors: Pedro P. Romero, Ricardo López, Carlos JiménezAbstract:(A) Detailed matrix 2012, 245 economic sectors. (B) Summary matrix 2012, 71 economic sectors. (C) Matrix 2010, 71 economic sectors. (D) Matrix 2007, 71 economic sectors. (E) Matrix 1995, 34 economic sectors. Log-log plots of the empirical counter-cumulative density functions of the weighted second-order Outdegree.
-
CCDF first-order weighted Outdegree input-output matrices 1995–2012.
2018Co-Authors: Pedro P. Romero, Ricardo López, Carlos JiménezAbstract:(A) Detailed matrix 2012, 245 economic sectors. (B) Summary matrix 2012, 71 economic sectors. (C) Matrix 2010, 71 economic sectors. (D) Matrix 2007, 71 economic sectors. (E) Matrix 1995, 34 economic sectors. Log-log plots of the empirical counter-cumulative density functions (CCDF) of the weighted first-order Outdegree.
Hosam M Mahmoud - One of the best experts on this subject based on the ideXlab platform.
-
on nodes of small degrees and degree profile in preferential dynamic attachment circuits
Methodology and Computing in Applied Probability, 2020Co-Authors: Panpan Zhang, Hosam M MahmoudAbstract:We investigate the joint distribution of nodes of small degrees and the degree profile in preferential dynamic attachment circuits. In particular, we study the joint asymptotic distribution of the number of the nodes of Outdegree 0 (terminal nodes) and Outdegree 1 in a very large circuit. The expectation and variance of the number of those two types of nodes are both asymptotically linear with respect to the age of the circuit. We show that the numbers of nodes of Outdegree 0 and 1 asymptotically follow a two-dimensional Gaussian law via multivariate martingale methods. The rate of convergence is derived analytically. We also study the exact distribution of the degree of a node, as the circuit ages, via a series of Polya-Eggenberger urn models with “hiccups” in between. The exact expectation and variance of the degree of nodes are determined by recurrence methods. Phase transitions of these degrees are discussed briefly. This is an extension of the abstract (Zhang 2016).
-
on nodes of small degrees and degree profile in preferential dynamic attachment circuits
arXiv: Probability, 2016Co-Authors: Panpan Zhang, Hosam M MahmoudAbstract:We investigate the joint distribution of nodes of small degrees and the degree profile in preferential dynamic attachment circuits. In particular, we study the joint asymptotic distribution of the number of the nodes of Outdegree $0$ (terminal nodes) and Outdegree $1$ in a very large circuit. The expectation and variance of the number of those two types of nodes are both asymptotically linear with respect to the age of the circuit. We show that the numbers of nodes of Outdegree $0$ and $1$ asymptotically follow a two-dimensional Gaussian law via multivariate martingale methods. We also study the exact distribution of the degree of a node, as the circuit ages, via a series of P\'olya-Eggenberger urn models with "hiccups" in between. The exact expectation and variance of the degree of nodes are determined by recurrence methods. Phase transitions of these degrees are discussed briefly. This is an extension of the abstract [20].
-
on the structure of random plane oriented recursive trees and their branches
Random Structures and Algorithms, 1993Co-Authors: Hosam M Mahmoud, Robert T Smythe, Jerzy SzymanskiAbstract:This paper is an investigation of the structural properties of random plane-oriented recursive trees and their branches. We begin by an enumeration of these trees and some general properties related to the Outdegrees of nodes. Using generalized Polya urn models we study the exact and limiting distributions of the size and the number of leaves in the branches of the tree. The exact distribution for the leaves in the branches is given by formulas involving second-order Eulerian numbers. A martingale central limit theorem for a linear combination of the number of leaves and the number of internal nodes is derived. The distribution of that linear combination is a mixture of normals with a beta distribution as its mixing density. The martingale central limit theorem allows easy determination of the limit laws governing the leaves in the branches. Furthermore, the asymptotic joint distribution of the number of nodes of Outdegree 0, 1 and 2 is shown to be trivariate normal. © 1993 John Wiley & Sons, Inc.
Pilipczuk Michal - One of the best experts on this subject based on the ideXlab platform.
-
On width measures and topological problems on semi-complete digraphs
'Elsevier BV', 2020Co-Authors: Fomin Fedor, Pilipczuk MichalAbstract:Under embargo until: 2021-02-01The topological theory for semi-complete digraphs, pioneered by Chudnovsky, Fradkin, Kim, Scott, and Seymour [10], [11], [12], [28], [43], [39], concentrates on the interplay between the most important width measures — cutwidth and pathwidth — and containment relations like topological/minor containment or immersion. We propose a new approach to this theory that is based on Outdegree orderings and new families of obstacles for cutwidth and pathwidth. Using the new approach we are able to reprove the most important known results in a unified and simplified manner, as well as provide multiple improvements. Notably, we obtain a number of efficient approximation and fixed-parameter tractable algorithms for computing width measures of semi-complete digraphs, as well as fast fixed-parameter tractable algorithms for testing containment relations in the semi-complete setting. As a direct corollary of our work, we also derive explicit and essentially tight bounds on duality relations between width parameters and containment orderings in semi-complete digraphs.acceptedVersio
-
On width measures and topological problems on semi-complete digraphs
'Elsevier BV', 2019Co-Authors: Fomin Fedor, Pilipczuk MichalAbstract:The topological theory for semi-complete digraphs, pioneered by Chudnovsky, Fradkin, Kim, Scott, and Seymour [10], [11], [12], [28], [43], [39], concentrates on the interplay between the most important width measures — cutwidth and pathwidth — and containment relations like topological/minor containment or immersion. We propose a new approach to this theory that is based on Outdegree orderings and new families of obstacles for cutwidth and pathwidth. Using the new approach we are able to reprove the most important known results in a unified and simplified manner, as well as provide multiple improvements. Notably, we obtain a number of efficient approximation and fixed-parameter tractable algorithms for computing width measures of semi-complete digraphs, as well as fast fixed-parameter tractable algorithms for testing containment relations in the semi-complete setting. As a direct corollary of our work, we also derive explicit and essentially tight bounds on duality relations between width parameters and containment orderings in semi-complete digraphs
