Compact distributed certification of geometric graph classes

DOI10.1016/J.JCSS.2025.103661MaRDI QIDQ6939609zbMATH OpenFDO

Authors Benjamin Jauregui, Pedro Montealegre, Ivan Rapaport

Publication date 21 August 2025

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

interval graphschordal graphspermutation graphsgeometric graph classesdistributed certificationlocal verification

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62) Distributed algorithms (68W15)

Cites work

• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• scientific article; zbMATH DE number 2080275 (Why is no real title available?)
• scientific article; zbMATH DE number 6850320 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• scientific article; zbMATH DE number 7832760 (Why is no real title available?)
• A meta-theorem for distributed certification
• A partial k-arboretum of graphs with bounded treewidth
• A simpler linear-time recognition of circular-arc graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Algorithmic graph theory and perfect graphs
• Alternation graphs
• Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
• Chaining algorithms for multiple genome comparison
• Characterizing circular-arc graphs
• Compact distributed certification of planar graphs
• Distributed minimum vertex coloring and maximum independent set in chordal graphs
• Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
• Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs
• Every planar graph is the intersection graph of segments in the plane (extended abstract)
• Graph Classes: A Survey
• Improved distributed algorithms for coloring interval graphs with application to multicoloring trees
• Linear-time recognition of circular-arc graphs
• Local certification of graphs on surfaces
• Locally checkable proofs in distributed computing
• Maximum weight independent set of circular-arc graph and its application
• Minimum weight feedback vertex sets in circle graphs
• Modular decomposition and transitive orientation
• On extremal problems of graphs and generalized graphs
• 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
• Randomized proof-labeling schemes
• Strictly chordal graphs are leaf powers
• The Complexity of Coloring Circular Arcs and Chords
• The Roberts characterization of proper and unit interval graphs
• The harmonious coloring problem is NP-complete for interval and permutation graphs
• Topics in Intersection Graph Theory
• Trapezoid graphs and their coloring
• Two strikes against perfect phylogeny
• What Can Be Certified Compactly? Compact local certification of MSO properties in tree-like graphs

This page was built for publication: Compact distributed certification of geometric graph classes

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