graph-theory   1221

« earlier    

d3-dag - Layout algorithms for visualizing directed acylic graphs
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
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
sarah-marie belcastro's personal site
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
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
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 
june 2018 by Vaguery
302 Found
Deep Dive Into Graph Traversals - Added December 13, 2017 at 10:04AM
algorithms  graph-theory 
june 2018 by xenocid
[1805.02213] Uniform Distribution of Kakutani Partitions Generated By Substitution Schemes
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
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
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
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
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
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 
april 2018 by liqweed

« earlier    

related tags

3blue1brown  `  acm  agent-based  ai  algebra  algo  algorithm  algorithms-explained  algorithms  anomaly-detection  api  approximation  art  article  aubrey-de-grey  aubrey_de_grey  automata  benchmark  big-data  biology  blog  book  books  boolean-networks  brain-scan  brueckner-networks  cellular-automata  chip-firing  chromatic  classification  clojure  clustering  code  cog-psych  cohesion  collective-intelligence  colors  combinatorics  commercial  complex-systems  complexology  composition-decomposition  compsci  computational-complexity  computational-geometry  computerscience  consider:classification  consider:feature-discovery  consider:find-shape-for-points  consider:inverse-problem  consider:looking-to-see  consider:mathematical-recreation  consider:out-of-box  consider:performance-measures  consider:rediscovery  consider:representation  consider:simulation  constraint-satisfaction  continued-fractions  d3.js  d3  d3js  data-science  data-structures  database  databases  dataset  db  detail-architecture  dev  dimension-reduction  discussion  distance-measures  distance  distributed  diversity  dynamical-systems  ecology  eden  emergence  enumeration  esoteric  evolution  evopsych  experimental-design  explanation  feature-construction  feature-extraction  food-webs  fractals  functional-programming  futurology  game-theory  game  geometry  giants  grantsanderson  graph-coloring  graph-database  graph-layout  graph-partitioning  graph-search  graph  graphdb  graphics  graphql  graphs  graphtheory  hacker-news  haskell  heuristics  horse-races  ideas  inference  insight  inspiration  intelligence  interactive  interview  iteration-recursion  js  json  knowledge-representation  learning  library  linear-algebra  liner-notes  local-global  looking-to-see  machine-learning  math  mathematical-recreations  mathematics  matrices  metrics  model  models  mooc  neo4j  network-models  network-structure  network-theory  neuro-nitgrit  neuro  nibble  nitty-gritty  nonlinear-dynamics  nudge-targets  number-theory  number  online  opensource  operations-research  optimization  orders  papers  path  pattern-formation  pdf  performance-measure  performance  philosophy  phylogenetics  plane-geometry  planning  probability-theory  programming  proof  psych-architecture  psychology  purdy-pitchers  puzzles  querying  questions  random-walks  rather-interesting  rdbms  read2of  reading  recursion  reduction  reference  representation  research  rewriting-systems  rigidity  robustness  ruby  sandpiles  serialization  service  sorting  spark  specification  speculation  sql  stamp-collecting  standards  statistics  streaming  strings  structure  study  symmetry  systematic-ad-hoc  tcs  teal  techtariat  theoretical-biology  tiling  time-complexity  to-cartoon-about  to-read  to-simulate  to-understand  to-w  to-write-about  to-write  topology  tutorial  tutorials  unsupervised  videos  visualization  whole-partial-many  wiki  youtube 

Copy this bookmark: