Ok, someone more familiar with graph theory tell me how to compute a minimum weight perfect matching on a complete graph with even-number of vertices? Or at least point me to a resource?
It's all either left as an exercise to the reader, extremely complex algorithms (Blossom or something?), or weird libraries, where apparently if I use it on complex graphs it's not necessary, but they then point me to even more complex papers.
Thought I had it solved but now it's returning a matching that's too small.
#graphtheory #computerscience #academia
Frühere Suchanfragen
Suchoptionen
#graphtheory
1 Beitrag1 Beteiligte*r0 Beiträge heute
Minimum spanning tree of a dithered image, 4096 vertices. Model: Swetlana
Without formal training, the way I modeled physical distribution system #Infrastructure for utilities districts in my #Django app evolved significantly over time.
As I learned more about graph theory and simulation, I figured out how to model for both the physical structure and the logical aspects of their interconnection and behavior in various scenarios.
#GraphTheory #WaterInfrastructure #Modeling
1/6
This video is a really pretty visualization of the A* pathfinding algorithm using #OpenStreetMap road network data for #Chicago and #Rome as examples.
www.youtube.com - YouTubeAuf YouTube findest du die angesagtesten Videos und Tracks. Außerdem kannst du eigene Inhalte hochladen und mit Freunden oder gleich der ganzen Welt teilen.
Refined my haiku visual a little today. I think it would be fun to see if there are any paths to take these words and traverse all of the haiku and if so - how many paths.
The dataset is Creative Commons if anyone wants to fork and play.
ALT
A post of @11011110 has reminded me that (after a year and a half lurking here) it's never too late for me to toot and pin an intro here.
I am a Canadian mathematician in the Netherlands, and I have been based at the University of Amsterdam since 2022. I also have some rich and longstanding ties to the UK, France, and Japan.
My interests are somewhere in the nexus of Combinatorics, Probability, and Algorithms. Specifically, I like graph colouring, random graphs, and probabilistic/extremal combinatorics. I have an appreciation for randomised algorithms, graph structure theory, and discrete geometry.
Around 2020, I began taking a more active role in the community, especially in efforts towards improved fairness and openness in science. I am proud to be part of a team that founded the journal, Innovations in Graph Theory (https://igt.centre-mersenne.org/), that launched in 2023. (That is probably the main reason I joined mathstodon!) I have also been a coordinator since 2020 of the informal research network, A Sparse (Graphs) Coalition (https://sparse-graphs.mimuw.edu.pl/), devoted to online collaborative workshops. In 2024, I helped spearhead the MathOA Diamond Open Access Stimulus Fund (https://www.mathoa.org/diamond-open-access-stimulus-fund/).
Until now, my posts have mostly been about scientific publishing and combinatorics.
#introduction
#openscience
#diamondopenaccess
#scientificpublishing
#openaccess
#RemoteConferences
#combinatorics
#graphtheory
#ExtremalCombinatorics
#probability
igt.centre-mersenne.org
Innovations in Graph Theory Innovations in Graph Theory
The Hidden Networks
That Rule Our World
S2 E50
Join us for a fascinating deep dive into the world of network analysis, where we explore Node2Vec - a groundbreaking algorithm that helps us understand the hidden communities within complex networks. Unlock profound insights about communities hidden within the vast connections surrounding us.
https://helioxpodcast.substack.com/p/the-hidden-networks-that-rule-our
#NetworkAnalysis #AI #ComplexSystems #GraphTheory #Node2Vec #NeuralNetworks #SocialNetworks #Podcast
Mathematics opens black box of AI decision-making
https://phys.org/news/2025-01-mathematical-technique-black-ai-decision.html
* understanding how neural networks (NN) make decisions
* poorly understood process in machine learning
Image segmentation w. traveling waves in exactly solvable recurrent NN
https://www.pnas.org/doi/10.1073/pnas.2321319121
* RNN performing simple image segmentation, also exactly mathematically solvable
* math understanding precisely how int. connections w/i NN create visual computations
ALT
Unlocking the Power of Treewidth: A Deep Dive into Graph Theory's Hidden Gem
Treewidth, a crucial concept in graph theory, is revolutionizing fields from game theory to network science. This article explores its definitions, computational significance, and wide-ranging applica...
ALT
Revolutionizing Mathematics: The Rise of Automated Conjecturing with TxGraffiti
In a groundbreaking advancement for the field of mathematics, the newly introduced program TxGraffiti is set to automate the generation of mathematical conjectures, particularly within graph theory. T...
ALT
I'm doing some of my "follow the instructions for a change" #Sashiko, and came upon a bit that I think means I can't do everything that's left without a lot of stopping and starting.
Then I realised I have an actual graph theorist in the house who might see something I'd missed.
So I checked with @ColinTheMathmo, and he did spot something I'd missed, but it confirmed the impossibility.
I'll have to fudge it...
Computer Scientists Establish the Best Way to Traverse a Graph
— Quanta Magazine
｢ Dijkstra credited his algorithm’s enduring appeal in part to its unusual origin story. “Without pencil and paper you are almost forced to avoid all avoidable complexities,” he said ｣
Quanta Magazine · Computer Scientists Establish the Best Way to Traverse a Graph | Quanta MagazineDijkstra’s algorithm was long thought to be the most efficient way to find a graph’s best routes. Researchers have now proved that it’s “universally optimal.”
I wrote a long ass article where I played around with visual representations of the Java Heap!
https://blog.p-y.wtf/rendering-the-java-heap-as-a-treemap
Has anyone explored this space?
P-Y's blog · Rendering the Java heap as a Treemap
Antwortete P-Y
This problem also generalizes at every layer of the dominator tree: even if we didn't have multiple sources / gc roots, we could render a tree map with a few big blocks but then a few levels down we'd find many many tiny nodes with a mostly flat hierarchy.
This means leveraging a classic dominators algorithm to render the Java heap as a TreeMap isn't terribly useful.
Antwortete P-Y
As we saw, gc root nodes are dominated by the virtual root of all roots.
What's happening is we have objects reachables (directly or indirectly) through multiple gc roots, where the only way to make these objects unreachable is to clear N gc roots.
Any such node is dominated by the virtual root.
And unfortunately this property is recursive, these nodes are now effectively acting like new gc roots from a dominator standpoint.
Hence many many roots.
Antwortete P-Y
If you've seen a TreeMap representation of the file system before, you know that the purpose is exactly the same: "which directory & files are using all my disk / where should I go clean things"
So, showing a TreeMap based on the dominator graph of a Java heap makes a ton of sense!
I was surprised I've never seen any tool that does that. It feels like it'd be a very intuitive representation of the Java heap.
So I'm working on this idea of representing a Java heap visually as a TreeMap.
"A treemap is a data visualization technique that uses nested rectangles to represent hierarchical data". The surface of the rectangle is proportional to the size of a node, which is typically the sum of the size of its child nodes.
You've probably seen TreeMap used to represent directory sizes on file system (also, Sunburst chart).
Hey Mastodon! 
Here is our #introduction post: We are the Data Visualization Lab at Khoury College of Computer Sciences at Northeastern University. You can find more about our work here: https://vis.khoury.northeastern.edu/
We'd love to be connected to more folks and labs in the realms of #DataVisualization #HCI #xAI #AR #VR #VisualAnalytics #PhD #Research
Our lab has been applying visualization to domain areas like #accessibility #UAVs #Genetics #Privacy #Pedagogy #Networks #GraphTheory
Say hi!
vis.khoury.northeastern.eduKhoury Vis Lab, Northeastern UniversityFront page Khoury Vis Lab, Northeastern University
Hello!
After a few days figuring out Mastodon with the help of the folks at QOTO, I will formally introduce myself in order to pin this in my profile :)
My name is Abde and I am a computer scientist. My main domain is #NumericalCalculus and #ParallelComputing. I am currently a PhD student at the Université Libre de Bruxelles (#belgium) and working on porting numerical solvers for simulations on the GPU using #CUDA. You may find my first paper here: https://etna.math.kent.edu/vol.55.2022/pp687-705.dir/pp687-705.pdf
Other research interests are #complexity #computability #graphtheory #geometry #discretemath
I also work as a #VirtualReality developer. My current professional interests are #simulations #numericalcalculus #geometry. We also contribute in several #opensource projects. Most of my work is done in #Unity3D, so feel free to ask any questions!
As a hobby I do some #gamedev and also #musicproduction. I will share some snippets of what I do here, but for now I am focusing in crafting my art by producing #housemusic in #bitwig.
Please enjoy! I am not the most active but I am looking to build my Mastodon network, so feel free to follow and I will follow back :)
OK, this seems fun, so here's my #introduction
I'm a computer nerd from Germany, and finished my masters degree this year. I wrote my thesis about the monitoring of #p2p #botnets, the detection thereof using #graphtheory and how to prevent detection using a #collaborated #crawling approach. Beside that I did some #sSoftwareEngineering professionally and for fun.
I am generally interested in #malware, mostly oldschool parasitic viruses.
Sometimes I play #CTF.
Currently I'm looking to get into #InfoSec professionally or academically.
Other stuff I enjoy includes #rust, #linux, #OpenSource, #selfhosing, #NixOS, #FunctionalProgamming and #AnalogPhotograpgy