Generalising the maximum independent set algorithm via Boolean networks

DOI10.1016/J.IC.2025.105266MaRDI QIDQ7021343zbMATH OpenFDO

Authors Maximilien Gadouleau, David C. Kutner

Publication date 28 February 2025

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IC.2025.105266

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A biological solution to a fundamental distributed computing problem
• Beeping a maximal independent set
• Communicating with beeps
• Connectivity and dynamics for random subgraphs of the directed cube
• Dangerous reference graphs and semantic paradoxes
• Design patterns in beeping algorithms: examples, emulation, and analysis
• Digraphs
• Disjunctive networks and update schedules
• Distributed Maximal Independent Set using Small Messages
• Dynamics of positive automata networks
• Fixing monotone Boolean networks asynchronously
• From kernels in directed graphs to fixed points and negative cycles in Boolean networks
• scientific article; zbMATH DE number 6472574 (Why is no real title available?)
• Itérations sur des ensembles finis et automates cellulaires contractants
• Local computation of maximal independent set
• Maximum number of fixed points in AND-OR-NOT networks
• On Fixable Families of Boolean Networks
• Paradox without Self-Reference
• Reducibility among combinatorial problems
• Self-stabilizing systems in spite of distributed control
• Survey of local algorithms
• Synchronism versus asynchronism in monotonic Boolean automata networks
• Synchronizing Boolean networks asynchronously

This page was built for publication: Generalising the maximum independent set algorithm via Boolean networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7021343)