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

DOI10.1007/978-3-031-09993-9_12MaRDI QIDQ2097349zbMATH OpenOpenAlexFDO

Authors Benjamin Jauregui, Pedro Montealegre, Ivan Rapaport

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

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

Cited in

(2)

• Interactive proofs for social graphs
• Local certification of geometric graph classes

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

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