graph-theory   1200

« earlier    

ekoontz/dag-unify: Unification of Directed Acyclic Graphs in Clojure
A Clojure library for combining directed acyclic graphs (DAGs) via unification. Unification is similar to merge (, except that if arguments have the same keys, the arguments' values for those keys will be recursively combined via unification to yield the value for the key in the combined map.
Clojure  library  graph-theory  algorithms 
6 hours ago by Vaguery
Engelberg/ubergraph: An all-purpose Clojure graph data structure that implements Loom protocols and more.
Ubergraph is a versatile, general-purpose graph data structure for Clojure. It is designed to complement and extend Loom, a popular Clojure collection of graph protocols and algorithms.
graph-theory  algorithms  Clojure  library  to-understand 
6 hours ago by Vaguery
GraphX - Apache Spark's API for graphs and graph-parallel computation
Apache Spark's API for graphs and graph-parallel computation.
Seamlessly work with both graphs and collections.
GraphX unifies ETL, exploratory analysis, and iterative graph computation within a single system. You can view the same data as both graphs and collections, transform and join graphs with RDDs efficiently, and write custom iterative graph algorithms using the Pregel API.
graph-theory  Spark  opensource  streaming  big-data 
5 days ago by liqweed
[1712.08373] Notes on complexity of packing coloring
A packing k-coloring for some integer k of a graph G=(V,E) is a mapping
φ:V→{1,…,k} such that any two vertices u,v of color φ(u)=φ(v) are in distance at least φ(u)+1. This concept is motivated by frequency assignment problems. The \emph{packing chromatic number} of G is the smallest k such that there exists a packing k-coloring of G.
Fiala and Golovach showed that determining the packing chromatic number for chordal graphs is \NP-complete for diameter exactly 5. While the problem is easy to solve for diameter 2, we show \NP-completeness for any diameter at least 3. Our reduction also shows that the packing chromatic number is hard to approximate within n1/2−ε for any ε>0.
In addition, we design an \FPT algorithm for interval graphs of bounded diameter. This leads us to exploring the problem of finding a partial coloring that maximizes the number of colored vertices.
graph-theory  algorithms  combinatorics  proof  approximation  nudge-targets  consider:looking-to-see  consider:feature-discovery 
5 days ago by Vaguery
[1609.00088] Statistics on bargraphs viewed as cornerless Motzkin paths
A bargraph is a self-avoiding lattice path with steps U=(0,1), H=(1,0) and D=(0,−1) that starts at the origin and ends on the x-axis, and stays strictly above the x-axis everywhere except at the endpoints. Bargraphs have been studied as a special class of convex polyominoes, and enumerated using the so-called wasp-waist decomposition of Bousquet-M\'elou and Rechnitzer. In this paper we note that there is a trivial bijection between bargraphs and Motzkin paths without peaks or valleys. This allows us to use the recursive structure of Motzkin paths to enumerate bargraphs with respect to several statistics, finding simpler derivations of known results and obtaining many new ones. We also count symmetric bargraphs and alternating bargraphs. In some cases we construct statistic-preserving bijections between different combinatorial objects, proving some identities that we encounter along the way.
combinatorics  representation  enumeration  graph-theory  feature-extraction  to-write-about 
27 days ago by Vaguery
I don’t understand Graph Theory. – freeCodeCamp
Graph theory represents one of the most important and interesting areas in computer science, and at the same time the most misunderstood (at least by me, no stats). Understanding and using graphs…
graph-theory  graphs  algorithm  math  algorithms  dev  learning  algo  article  code 
29 days ago by otlib

« earlier    

related tags

3blue1brown  `  academia  acm  agent-based  algebra  algo  algorithm  algorithms-explained  algorithms  angular  anomaly-detection  approximation  article  asia  automata  benchmark  benchmarking  big-data  biology  book  books  boolean-networks  brueckner-networks  c++  cellular-automata  chemistry  chip-firing  classification  clojure  clustering  cnns  code  collective-intelligence  combinatorics  commercial  complexology  composition-decomposition  compsci  computational-complexity  computational-geometry  computerscience  consider:classification  consider:evolutionary-algorithms  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  data-synthesis  database  databases  db  dev  discussion  distance-measures  distributed  dynamical-systems  ecology  emergence  enumeration  esoteric  experimental-design  explanation  feature-construction  feature-extraction  food-webs  functional_programming_concepts  game-theory  game  gans  gcns  generative-models  geometry  github  grantsanderson  graph-layout  graph-partitioning  graph  graphdb  graphics  graphs  graphtheory  hacker-news  haskell  heuristics  higher-ed  horse-races  inference  insight  inspiration  interactive  interview  inverse-problems  iteration-recursion  js  json  knowledge-representation  korea  learning  library  linear-algebra  liner-notes  local-global  looking-to-see  machine-learning  maps  math  mathematical-recreations  mathematics  matrices  metrics  model  mooc  neo4j  network-structure  network-theory  news  nibble  nonlinear-dynamics  nudge-targets  opensource  operations-research  optimization  orders  org:inst  org:mag  org:sci  papers  pattern-formation  performance-measure  performance  phylogenetics  plane-geometry  planning  popsci  probability-theory  profile  programming-practice  programming  proof  purdy-pitchers  puzzles  python  querying  questions  random-walks  rather-interesting  rdbms  read2of  reading  reference  representation  research  rigidity  robustness  ruby  sandpiles  serialization  sorting  spark  specification  sql  stamp-collecting  standards  statistics  streaming  strings  sydney-papers-meetup  symmetry  tcs  techtariat  tensorflow  theoretical-biology  time-complexity  to-cartoon-about  to-read  to-simulate  to-understand  to-w  to-write-about  to-write  tutorial  unsupervised  videos  visualization  widgets  wiki  youtube 

Copy this bookmark: