Scheduling wireless ad hoc networks in polynomial time using claw-free conflict graphs

In this paper, we address the scheduling problem in wireless ad hoc networks by exploiting the computational advantage that comes when such scheduling problems can be represented by claw-free conflict graphs. It is possible to formulate a scheduling problem of network coded flows as finding maximum weighted independent set (MWIS) in the conflict graph of the network. We consider activation of hyperedges in a hypergraph to model a wireless broadcast medium. We show that the conflict graph of certain wireless ad hoc networks are claw-free. It is known that finding MWIS of a general graph is NP-hard, but in a claw-free conflict graph, it is possible to apply Minty's or Faenza et al.'s algorithms in polynomial time. We discuss our approach on some sample networks.

• Publication year

  2017

• Venue

  IEEE International Symposium on Personal, Indoor and Mobile Radio Communications

• Publication date

  2017-10-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/PIMRC.2017.8292404arXiv 1711.01620
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition

  2014cited by this paper
• Scheduling for Network-Coded Multicast

  2012cited by this paper
• Scheduling for Network Coded Multicast: A Conflict Graph Formulation

  2008cited by this paper
• A Systematic Approach to Network Coding Problems using Conflict Graphs

  2006cited by this paper
• On the Complexity of Scheduling in Wireless Networks

  2006cited by this paper
• Maximum weighted matching with interference constraints

  2006cited by this paper
• The structure of claw-free graphs

  2005cited by this paper
• Minimum-cost multicast over coded packet networks

  2005cited by this paper
• A revision of Minty's algorithm for finding a maximum weight stable set of a claw-free graph

  2001cited by this paper
• RHEINISCH-WESTFÄLISCHE TECHNISCHE HOCHSCHULE AACHEN

  2001influential reference
• Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks

  1990cited by this paper
• Scheduling broadcasts in multihop radio networks

  1990cited by this paper
• Link scheduling in polynomial time

  1988cited by this paper
• Some complexity results about packet radio networks

  1983cited by this paper
• On maximal independent sets of vertices in claw-free graphs

  1980cited by this paper

• Generation of quantum phases of matter and finding a maximum-weight independent set of unit-disk graphs using Rydberg atoms

  2024cites this paper
• Age of Information Minimizing Dynamic User Pairing in Downlink NOMA Systems

  2023cites this paper
• Structured Hypergraphs in Cellular Mobile Communication Systems

  2023cites this paper
• The Structure of Hypergraphs Arising in Cellular Mobile Communication Systems

  2022cites this paper
• Gaussian 1-2-1 Networks: Capacity Results for mmWave Communications

  2021cites this paper
• A Novel Method for Scheduling of Wireless Ad Hoc Networks in Polynomial Time

  2021cites this paper
• Performance analysis of a distributed algorithm for admission control in wireless networks under the 2-hop interference model

  2020cites this paper
• Separation routine and extended formulations for the stable set problem in claw-free graphs

  2020cites this paper
• Performance Guarantees of Distributed Algorithms for QoS in Wireless Ad Hoc Networks

  2018influential citation
• High-Priority Minimum-Interference Channel Assignment in Multi-Radio Multi-Channel Wireless Networks

  2018cites this paper
• Performance of distributed algorithms for QoS in wireless ad hoc networks: arbitrary networks under the primary interference model, and line networks under the protocol interference model

  2018influential citation
• Nearly Optimal Scheduling of Wireless Ad Hoc Networks in Polynomial Time

  2017cites this paper
• Inductive $$k$$k-independent graphs and c-colorable subgraphs in scheduling: a review

  2017cites this paper