Saxena et al., 2026 - Google Patents

Exploration on Highly Dynamic Graphs

Saxena et al., 2026

View PDF
Document ID
7076409405489921622
Author
Saxena A
Mondal K
Publication year
Publication venue
arXiv preprint arXiv:2601.13047

External Links

Snippet

We study the exploration problem by mobile agents in two prominent models of dynamic graphs: $1 $-Interval Connectivity and Connectivity Time. The $1 $-Interval Connectivity model was introduced by Kuhn et al.~[STOC 2010], and the Connectivity Time model was …
Continue reading at arxiv.org (PDF) (other versions)

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30946—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures
    • G06F17/30958—Graphs; Linked lists
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/02—Details
    • H04L12/26—Monitoring arrangements; Testing arrangements
    • H04L12/2602—Monitoring arrangements
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L41/00—Arrangements for maintenance or administration or management of packet switching networks
    • H04L41/12—Arrangements for maintenance or administration or management of packet switching networks network topology discovery or management
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F15/00—Digital computers in general; Data processing equipment in general
    • G06F15/16—Combinations of two or more digital computers each having at least an arithmetic unit, a programme unit and a register, e.g. for a simultaneous processing of several programmes
    • G06F15/163—Interprocessor communication
    • G06F15/173—Interprocessor communication using an interconnection network, e.g. matrix, shuffle, pyramid, star, snowflake
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L41/00—Arrangements for maintenance or administration or management of packet switching networks
    • H04L41/06—Arrangements for maintenance or administration or management of packet switching networks involving management of faults or events or alarms
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/02—Topology update or discovery
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/12—Shortest path evaluation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/28—Data switching networks characterised by path configuration, e.g. local area networks [LAN], wide area networks [WAN]
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/04—Interdomain routing, e.g. hierarchical routing

Similar Documents

Publication Publication Date Title
Dobrev et al. Mobile search for a black hole in an anonymous ring
Flocchini et al. On the exploration of time-varying networks
Flocchini et al. Exploration of periodically varying graphs
Flocchini et al. Computing without communicating: Ring exploration by asynchronous oblivious robots
Kshemkalyani et al. Efficient dispersion of mobile robots on dynamic graphs
Flocchini et al. Searching for black holes in subways
Casteigts et al. Deterministic algorithms in dynamic networks: Problems, analysis, and algorithmic tools
Markou et al. Dangerous graphs
Flocchini et al. Distributed security algorithms for mobile agents
Chalopin et al. Tight bounds for black hole search with scattered agents in synchronous rings
Miller et al. Fast byzantine gathering with visibility in graphs
Di Luna et al. Black hole search in dynamic rings
Markou et al. Black hole search and exploration in unoriented tori with synchronous scattered finite automata
Anandkumar et al. Topology discovery of sparse random graphs with few participants
Casteigts Finding structure in dynamic networks
CN102938918A (en) Method, device and system for managing wireless sensor network (WSN)
Saxena et al. Exploration on Highly Dynamic Graphs
Das et al. Distributed exploration of an unknown graph
Gorain et al. Collaborative dispersion by silent robots
Flocchini et al. Ping pong in dangerous graphs: Optimal black hole search with pure tokens
Das et al. Broadcasting with mobile agents in dynamic networks
Saxena et al. Natural Calamities Demand More Rescuers: Exploring Connectivity Time Dynamic Graphs
Ilcinkas Setting port numbers for fast graph exploration
Dobrev et al. Black Hole Search by Mobile Agents in Hypercubes and Related Networks.
Bonnet et al. Looking for the Weakest Failure Detector for k-Set Agreement in Message-Passing Systems: Is the End of the Road?