Random maximal independent sets and the unfriendly theater seating arrangement problem

DOI10.1016/j.disc.2009.03.049zbMath1184.90061OpenAlexW2106547329MaRDI QIDQ1044988

Danny Krizanc, Evangelos Kranakis, Konstantinos Georgiou

Publication date: 15 December 2009

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

Full work available at URL: https://doi.org/10.1016/j.disc.2009.03.049

zbMATH Keywords

graph theoryexpected valueasymptotic limit

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (4)

Per-site occupancy in the discrete parking problem ⋮ Maintaining privacy on a line ⋮ Random unfriendly seating arrangement in a dining table ⋮ Excuse me! or the courteous theatregoers' problem

Uses Software

• Maple

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Planar lattice gases with nearest-neighbor exclusion
• Several constants arising in statistical mechanics
• Parking arcs on the circle with applications to one-dimensional communication networks
• Breakdown of elasticity theory for jammed hard-particle packings: conical nonlinear constitutive theory
• The Number of Independent Sets in a Grid Graph
• Critical and tricritical hard objects on bicolourable random lattices: exact solutions
• Combinatorics of bicubic maps with hard particles

This page was built for publication: Random maximal independent sets and the unfriendly theater seating arrangement problem