A5048684673- Optimization and Search Problems
- Complexity and Algorithms in Graphs
- Advanced Graph Theory Research
- Scheduling and Optimization Algorithms
- Artificial Intelligence in Games
- Data Management and Algorithms
- Machine Learning and Algorithms
- Graph Labeling and Dimension Problems
- Distributed systems and fault tolerance
- Interconnection Networks and Systems
- Mobile Agent-Based Network Management
- Modular Robots and Swarm Intelligence
- Distributed and Parallel Computing Systems
- Graph theory and applications
- Algorithms and Data Compression
- Game Theory and Applications
- Computational Geometry and Mesh Generation
- Constraint Satisfaction and Optimization
- Cellular Automata and Applications
- Robotic Path Planning Algorithms
- Graph Theory and Algorithms
- DNA and Biological Computing
- Metaheuristic Optimization Algorithms Research
- Caching and Content Delivery
- Mobile Crowdsensing and Crowdsourcing
Gdańsk University of Technology
2014-2024
Institut national de recherche en informatique et en automatique
2014
Laboratoire d'Informatique Algorithmique: Fondements et Applications
2014
Abstract Depth first search is a natural algorithmic technique for constructing closed route that visits all vertices of graph. The length such equals, in an edge-weighted tree, twice the total weight edges tree and this asymptotically optimal over exploration strategies. This paper considers variant strategies where each bounded by positive integer B (e.g. due to limited energy resources searcher). objective cover T using minimum number routes, starting ending at root being most . To end,...
It is proven that the connected pathwidth of any graph $G$ at most $2\cdot\textup{pw}(G)+1$, where $\textup{pw}(G)$ $G$. The method constructive, i.e., it yields an efficient algorithm for a given path decomposition width $k$ computes $2k+1$. running time $O(dk^2)$, $d$ number "bags" in input decomposition. motivation studying decompositions comes from connection between and search graph. One advantages above bound inequality $\textup{\texttt{cs}}(G)\leq 2\textup{\texttt{s}}(G)+3$,...
We study the problem of leader election among mobile agents operating in an arbitrary network modeled as undirected graph. Nodes are unlabeled and all identical. Hence only way to elect a is by exploiting asymmetries their initial positions Agents do not know graph or it, hence they must gain this knowledge navigating share it with other accomplish election. This can be done using meetings agents, which difficult because asynchronous nature: adversary has total control over speed agents....
The \emph{rotor-router mechanism} was introduced as a deterministic alternative to the random walk in undirected graphs. In this model, set of $k$ identical walkers is deployed parallel, starting from chosen subset nodes, and moving around graph synchronous steps. During process, each node maintains cyclic ordering its outgoing arcs, successively propagates which visit it along arcs round-robin fashion, according fixed ordering. We consider \emph{cover time} such system, i.e., number steps...
We consider the following generalization of binary search problem. A strategy is required to locate an unknown target node $t$ in a given tree $T$. Upon querying $v$ tree, receives as reply indication connected component $T\setminus\{v\}$ containing $t$. The cost each by known non-negative weight function, and considered objective minimize total query for worst-case choice target. Designing optimal weighted instance be strongly NP-hard, contrast unweighted variant problem which can solved...