**graph-theory**1221

d3-dag - Layout algorithms for visualizing directed acylic graphs

4 days ago by liqweed

This module implements a data structures for manipulating DAGs that mimics the API of d3-hierarchy as much as possible.

d3
graphs
graph-theory
opensource
visualization
algorithms
4 days ago by liqweed

Unigraph – The world's largest Knowledge Graph

21 days ago by liqweed

Creating the infrastructure and building the web of interconnected data, a datasource at the time. Innovative approach to big data storage and retrieval combined with the best practices in evolving ontology design power the distributed Knowledge Graph of the future and its real-time data API.

dataset
API
graph-theory
GraphQL
online
service
querying
21 days ago by liqweed

John Williamson on Twitter: "First 1e6 integers, represented as binary vectors indicating their prime factors, and laid out using the sparse matrix support in @leland_mcinnes's UMAP dimensionality reduction algorithm. This is from a 1000000x78628 (!) bina

mathematics number-theory visualization rather-interesting graph-theory graph-layout dimension-reduction to-write-about

28 days ago by Vaguery

mathematics number-theory visualization rather-interesting graph-theory graph-layout dimension-reduction to-write-about

28 days ago by Vaguery

sarah-marie belcastro's personal site

5 weeks ago by abstresma

she's a mathematician (topological graph theorist (studies how meshy things act on shapey things)). her site is full of useful information ranging from lists of cool things on the internet to her research papers and dissertation (as you find on these types of sites) to a list of teal-haired female mathematicians to tutorials about graph theory to mathematical knitting

mathematics
blog
graph-theory
topology
teal
art
5 weeks ago by abstresma

Functional programming with graphs

9 weeks ago by xenocid

Functional programming with graphs - Added December 21, 2017 at 02:49PM

functional-programming
graph-theory
read2of
9 weeks ago by xenocid

[1802.03905] How to Match when All Vertices Arrive Online

june 2018 by Vaguery

We introduce a fully online model of maximum cardinality matching in which all vertices arrive online. On the arrival of a vertex, its incident edges to previously-arrived vertices are revealed. Each vertex has a deadline that is after all its neighbors' arrivals. If a vertex remains unmatched until its deadline, the algorithm must then irrevocably either match it to an unmatched neighbor, or leave it unmatched. The model generalizes the existing one-sided online model and is motivated by applications including ride-sharing platforms, real-estate agency, etc.

We show that the Ranking algorithm by Karp et al. (STOC 1990) is 0.5211-competitive in our fully online model for general graphs. Our analysis brings a novel charging mechanic into the randomized primal dual technique by Devanur et al. (SODA 2013), allowing a vertex other than the two endpoints of a matched edge to share the gain. To our knowledge, this is the first analysis of Ranking that beats 0.5 on general graphs in an online matching problem, a first step towards solving the open problem by Karp et al. (STOC 1990) about the optimality of Ranking on general graphs. If the graph is bipartite, we show that the competitive ratio of Ranking is between 0.5541 and 0.5671. Finally, we prove that the fully online model is strictly harder than the previous model as no online algorithm can be 0.6317<1−1e-competitive in our model even for bipartite graphs.

algorithms
dynamical-systems
graph-theory
rather-interesting
computational-complexity
to-write-about
to-simulate
We show that the Ranking algorithm by Karp et al. (STOC 1990) is 0.5211-competitive in our fully online model for general graphs. Our analysis brings a novel charging mechanic into the randomized primal dual technique by Devanur et al. (SODA 2013), allowing a vertex other than the two endpoints of a matched edge to share the gain. To our knowledge, this is the first analysis of Ranking that beats 0.5 on general graphs in an online matching problem, a first step towards solving the open problem by Karp et al. (STOC 1990) about the optimality of Ranking on general graphs. If the graph is bipartite, we show that the competitive ratio of Ranking is between 0.5541 and 0.5671. Finally, we prove that the fully online model is strictly harder than the previous model as no online algorithm can be 0.6317<1−1e-competitive in our model even for bipartite graphs.

june 2018 by Vaguery

302 Found

june 2018 by xenocid

Deep Dive Into Graph Traversals - Added December 13, 2017 at 10:04AM

algorithms
graph-theory
june 2018 by xenocid

How do we measure the complexity of a graph?

june 2018 by chr7stos

Metrics for graph complexity

graph-theory
june 2018 by chr7stos

[1805.02213] Uniform Distribution of Kakutani Partitions Generated By Substitution Schemes

may 2018 by Vaguery

The main result of this paper is a proof of uniform distribution for a large family of sequences of partitions, constituting a generalization of a result of Kakutani regarding partitions of the unit interval. A sequence is defined according to a multiscale substitution scheme on a set of prototiles, which is a set of substitution rules determining a tiling of each prototile by rescaled copies of the prototiles at hand. Given a multiscale substitution scheme, a succession of substitutions of tiles is used to define a sequence of partitions, which is studied using a directed weighted graph associated with the scheme.

tiling
recursion
graph-theory
fractals
to-understand
rewriting-systems
may 2018 by Vaguery

[1607.01117] Anagram-free Graph Colouring

may 2018 by Vaguery

An anagram is a word of the form WP where W is a non-empty word and P is a permutation of W. We study anagram-free graph colouring and give bounds on the chromatic number. Alon et al. (2002) asked whether anagram-free chromatic number is bounded by a function of the maximum degree. We answer this question in the negative by constructing graphs with maximum degree 3 and unbounded anagram-free chromatic number. We also prove upper and lower bounds on the anagram-free chromatic number of trees in terms of their radius and pathwidth. Finally, we explore extensions to edge colouring and k-anagram-free colouring.

graph-theory
algorithms
graph-coloring
feature-construction
nudge-targets
consider:looking-to-see
computational-complexity
may 2018 by Vaguery

[1708.09571] Anagram-free colourings of graph subdivisions

may 2018 by Vaguery

An anagram is a word of the form WP where W is a non-empty word and P is a permutation of W. A vertex colouring of a graph is anagram-free if no subpath of the graph is an anagram. Anagram-free graph colouring was independently introduced by Kam\v{c}ev, {\L}uczak and Sudakov and ourselves. In this paper we introduce the study of anagram-free colourings of graph subdivisions. We show that every graph has an anagram-free 8-colourable subdivision. The number of division vertices per edge is exponential in the number of edges. For trees, we construct anagram-free 10-colourable subdivisions with fewer division vertices per edge. Conversely, we prove lower bounds, in terms of division vertices per edge, on the anagram-free chromatic number for subdivisions of the complete graph and subdivisions of complete trees of bounded degree.

combinatorics
graph-theory
graph-coloring
computational-complexity
rather-interesting
nudge-targets
consider:looking-to-see
may 2018 by Vaguery

[1803.07694] Defective and Clustered Graph Colouring

may 2018 by Vaguery

Consider the following two ways to colour the vertices of a graph where the requirement that adjacent vertices get distinct colours is relaxed. A colouring has "defect" d if each monochromatic component has maximum degree at most d. A colouring has "clustering" c if each monochromatic component has at most c vertices. This paper surveys research on these types of colourings, where the first priority is to minimise the number of colours, with small defect or small clustering as a secondary goal. List colouring variants are also considered. The following graph classes are studied: outerplanar graphs, planar graphs, graphs embeddable in surfaces, graphs with given maximum degree, graphs with given maximum average degree, graphs excluding a given subgraph, graphs with linear crossing number, linklessly or knotlessly embeddable graphs, graphs with given Colin de Verdi\`ere parameter, graphs with given circumference, graphs excluding a fixed graph as an immersion, graphs with given thickness, graphs with given stack- or queue-number, graphs excluding Kt as a minor, graphs excluding Ks,t as a minor, and graphs excluding an arbitrary graph H as a minor. Several open problems are discussed.

combinatorics
graph-theory
algorithms
rather-interesting
computational-complexity
nudge-targets
consider:performance-measures
may 2018 by Vaguery

[1803.01422] DAGs with NO TEARS: Smooth Optimization for Structure Learning

april 2018 by Vaguery

Estimating the structure of directed acyclic graphs (DAGs, also known as Bayesian networks) is a challenging problem since the search space of DAGs is combinatorial and scales superexponentially with the number of nodes. Existing approaches rely on various local heuristics for enforcing the acyclicity constraint and are not well-suited to general purpose optimization packages for their solution. In this paper, we introduce a fundamentally different strategy: We formulate the structure learning problem as a smooth, constrained optimization problem over real matrices that avoids this combinatorial constraint entirely. This is achieved by a novel characterization of acyclicity that is not only smooth but also exact. The resulting nonconvex, constrained program involves smooth functions whose gradients are easy to compute and only involve elementary matrix operations. By using existing black-box optimization routines, our method uses global search to find an optimal DAG and can be implemented in about 50 lines of Python and outperforms existing methods without imposing any structural constraints.

graph-theory
combinatorics
algorithms
rather-interesting
computational-complexity
to-understand
to-write-about
nudge-targets
consider:looking-to-see
representation
april 2018 by Vaguery

TigerGraph - Fast, Scalable Graph Database & Graph Analytics Platform

april 2018 by liqweed

The World Fastest and Most Scalable Graph Platform

Through its Native Parallel Graph™ technology, TigerGraph represents what’s next in the graph database evolution: a complete, distributed, parallel graph computing platform supporting web-scale data analytics in real-time.

Combining the best ideas (MapReduce, Massively Parallel Processing, and fast data compression/decompression) with fresh development, TigerGraph delivers what you’ve been waiting for: the speed, scalability, and deep exploration/querying capability to extract more business value from your data.

graph-theory
database
commercial
distributed
big-data
querying
Through its Native Parallel Graph™ technology, TigerGraph represents what’s next in the graph database evolution: a complete, distributed, parallel graph computing platform supporting web-scale data analytics in real-time.

Combining the best ideas (MapReduce, Massively Parallel Processing, and fast data compression/decompression) with fresh development, TigerGraph delivers what you’ve been waiting for: the speed, scalability, and deep exploration/querying capability to extract more business value from your data.

april 2018 by liqweed

**related tags**

Copy this bookmark: