Distributed interactive proofs for the recognition of some geometric intersection graph classes

DOI10.1007/978-3-031-09993-9_12OpenAlexW4285107913MaRDI QIDQ2097349

Benjamin Jauregui, Ivan Rapaport, Pedro Montealegre

Publication date: 11 November 2022

Full work available at URL: https://arxiv.org/abs/2112.03206

zbMATH Keywords

distributed decisiondistributed interactive proofsintersection graph classesproof-labeling scheme

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer system organization (68Mxx) Communication complexity, information complexity (68Q11)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum weight independent sets and cliques in intersection graphs of filaments
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Trapezoid graphs and their coloring
• Linear-time recognition of circular-arc graphs
• An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
• Algorithmic graph theory and perfect graphs
• An \(O(n)\)-time algorithm for the paired domination problem on permutation graphs
• Randomized proof-labeling schemes
• Compact distributed certification of planar graphs
• On distributed Merlin-Arthur decision protocols
• Fast distance multiplication of unit-Monge matrices
• Proof labeling schemes
• The harmonious coloring problem is NP-complete for interval and permutation graphs
• Chaining algorithms for multiple genome comparison
• On the Enumeration and Counting of Minimal Dominating sets in Interval and Permutation Graphs
• On the Desirability of Acyclic Database Schemes
• Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
• Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete
• The Knowledge Complexity of Interactive Proof Systems
• The Complexity of Coloring Circular Arcs and Chords
• Topics in Intersection Graph Theory
• Graph Classes: A Survey
• Recognition of Circle Graphs
• Algebraic methods for interactive proof systems
• IP = PSPACE
• Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
• On the 2-Chain Subgraph Cover and Related Problems
• What Can be Computed Locally?
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
• The Power of Distributed Verifiers in Interactive Proofs
• Brief Announcement
• Interactive Distributed Proofs
• A Simpler Linear-Time Recognition of Circular-Arc Graphs
• Compact Distributed Certification of Planar Graphs
• Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs
• Improved distributed algorithms for coloring interval graphs with application to multicoloring trees
• Approximate proof-labeling schemes

This page was built for publication: Distributed interactive proofs for the recognition of some geometric intersection graph classes