On budget-constrained coverage in multi-interface networks: branchwidth and treewidth perspectives

DOI10.1016/J.DAM.2025.11.005MaRDI QIDQ6866655zbMATH OpenFDO

Authors Alessandro Aloisio, Alfredo Navarra

Publication date 28 January 2026

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2025.11.005

zbMATH Keywords

branchwidthcoveragemulti-interface networkparameterized complexitytreewidth

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10) Programming involving graphs or networks (90C35)

Cites work

• A novel dynamic programming heuristic for the quadratic knapsack problem
• Approximation of the quadratic knapsack problem
• Automata, Languages and Programming
• Balancing energy consumption for the establishment of multi-interface networks
• Cost minimization in wireless networks with a bounded and unbounded number of interfaces
• Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
• Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
• Energy consumption minimization in ad hoc wireless and multi-interface networks
• Energy-efficient communication in multi-interface wireless networks
• Equitable aggregations and multiple criteria analysis
• Fast FPT-approximation of branchwidth
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• Flow Problems in Multi-Interface Networks
• Graph edge coloring: a survey
• Graph minors. X: Obstructions to tree-decomposition
• Maximizing the overall end-user satisfaction of data broadcast in wireless mesh networks
• Maximum matching in multi-interface networks
• Minimize the maximum duty in multi-interface networks
• Parameterized algorithms
• Practical algorithms for branch-decompositions of planar graphs
• Semi-nice tree-decompositions: the best of branchwidth, treewidth and pathwidth with one algorithm
• STACS 2004
• Tour merging via branch-decomposition
• Using \(\ell^p\)-norms for fairness in combinatorial optimisation
• Worst-Case Analysis of a Placement Algorithm Related to Storage Allocation

This page was built for publication: On budget-constrained coverage in multi-interface networks: branchwidth and treewidth perspectives

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