graph-theory   1213

« earlier    

[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 
13 days ago by Vaguery
302 Found
Deep Dive Into Graph Traversals - Added December 13, 2017 at 10:04AM
algorithms  graph-theory 
14 days ago 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 
27 days ago 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 
28 days ago 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 
28 days ago 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 
28 days ago 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 
11 weeks ago 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 
11 weeks ago by liqweed
Society of Mind - Wikipedia
A core tenet of Minsky's philosophy is that "minds are what brains do". The society of mind theory views the human mind and any other naturally evolved cognitive systems as a vast society of individually simple processes known as agents. These processes are the fundamental thinking entities from which minds are built, and together produce the many abilities we attribute to minds. The great power in viewing a mind as a society of agents, as opposed to the consequence of some basic principle or some simple formal system, is that different agents can be based on different types of processes with different purposes, ways of representing knowledge, and methods for producing results.

This idea is perhaps best summarized by the following quote:

What magical trick makes us intelligent? The trick is that there is no trick. The power of intelligence stems from our vast diversity, not from any single, perfect principle. —Marvin Minsky, The Society of Mind, p. 308

The modular organization of human anatomical
brain networks: Accounting for the cost of wiring:
Brain networks are expected to be modular. However, existing techniques for estimating a network’s modules make it difficult to assess the influence of organizational principles such as wiring cost reduction on the detected modules. Here we present a modification of an existing module detection algorithm that allowed us to focus on connections that are unexpected under a cost-reduction wiring rule and to identify modules from among these connections. We applied this technique to anatomical brain networks and showed that the modules we detected differ from those detected using the standard technique. We demonstrated that these novel modules are spatially distributed, exhibit unique functional fingerprints, and overlap considerably with rich clubs, giving rise to an alternative and complementary interpretation of the functional roles of specific brain regions. Finally, we demonstrated that, using the modified module detection approach, we can detect modules in a developmental dataset that track normative patterns of maturation. Collectively, these findings support the hypothesis that brain networks are composed of modules and provide additional insight into the function of those modules.
books  ideas  speculation  structure  composition-decomposition  complex-systems  neuro  ai  psychology  cog-psych  intelligence  reduction  wiki  giants  philosophy  number  cohesion  diversity  systematic-ad-hoc  detail-architecture  pdf  study  neuro-nitgrit  brain-scan  nitty-gritty  network-structure  graphs  graph-theory  models  whole-partial-many  evopsych  eden  reference  psych-architecture  article 
11 weeks ago by nhaliday
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 
march 2018 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 
march 2018 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 
march 2018 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 
march 2018 by Vaguery

« earlier    

related tags

3blue1brown  `  acm  agent-based  ai  algebra  algo  algorithm  algorithms-explained  algorithms  anomaly-detection  approximation  article  aubrey-de-grey  aubrey_de_grey  automata  benchmark  benchmarking  big-data  biology  book  books  boolean-networks  brain-scan  brueckner-networks  cellular-automata  chemistry  chip-firing  chromatic  classification  clojure  clustering  cnns  code  cog-psych  cohesion  collective-intelligence  colors  combinatorics  commercial  complex-systems  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  detail-architecture  dev  discussion  distance-measures  distance  distributed  diversity  dynamical-systems  ecology  eden  emergence  enumeration  esoteric  evopsych  experimental-design  explanation  feature-construction  feature-extraction  food-webs  fractals  futurology  game-theory  game  generative-models  geometry  giants  grantsanderson  graph-coloring  graph-database  graph-layout  graph-partitioning  graph  graphdb  graphics  graphs  graphtheory  hacker-news  haskell  heuristics  horse-races  ideas  inference  insight  inspiration  intelligence  interactive  interview  inverse-problems  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-structure  network-theory  neuro-nitgrit  neuro  nibble  nitty-gritty  nonlinear-dynamics  nudge-targets  number  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  sorting  spark  specification  speculation  sql  stamp-collecting  standards  statistics  streaming  strings  structure  study  symmetry  systematic-ad-hoc  tcs  techtariat  tensorflow  theoretical-biology  tiling  time-complexity  to-cartoon-about  to-read  to-simulate  to-understand  to-w  to-write-about  to-write  tutorial  unsupervised  videos  visualization  whole-partial-many  wiki  youtube 

Copy this bookmark: