Zero knowledge and the chromatic number

DOI10.1006/JCSS.1998.1587zbMath0921.68089OpenAlexW2058422149MaRDI QIDQ1276168

Publication date: 6 October 1999

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

Full work available at URL: https://semanticscholar.org/paper/40265ae8a3e103dba2f471d9bc7dde377856fe5f

zbMATH Keywords

chromatic number zero-knowledge

Mathematics Subject Classification ID

Related Items (88)

Towards optimal lower bounds for clique and chromatic number. ⋮ Coloring Jacobians revisited: a new algorithm for star and~acyclic bicoloring ⋮ Detecting almost symmetries of graphs ⋮ A fast network-decomposition algorithm and its applications to constant-time distributed computation ⋮ Direct routing: Algorithms and complexity ⋮ Scheduling with conflicts: Online and offline algorithms ⋮ Distributed computing with advice: information sensitivity of graph coloring ⋮ Blocker size via matching minors ⋮ An improved algorithm for approximating the chromatic number of \(G_{n,p}\) ⋮ Local Construction and Coloring of Spanners of Location Aware Unit Disk Graphs ⋮ Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation ⋮ A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation ⋮ Coloring immersion-free graphs ⋮ On the Complexity of the Minimum Independent Set Partition Problem ⋮ On the intractability landscape of digraph intersection representations ⋮ Injective coloring of some subclasses of bipartite graphs and chordal graphs ⋮ On the complexity of deriving position specific score matrices from positive and negative sequences ⋮ Some recent progress and applications in graph minor theory ⋮ Complexity of Coloring Random Graphs ⋮ Network design under general wireless interference ⋮ Bisecting and \(D\)-secting families for set systems ⋮ On the complexity of injective colorings and its generalizations ⋮ A supernodal formulation of vertex colouring with applications in course timetabling ⋮ Average-case complexity of backtrack search for coloring sparse random graphs ⋮ Computing the partition function for graph homomorphisms with multiplicities ⋮ A pure labeled transition semantics for the applied pi calculus ⋮ The Hardness of Approximating Poset Dimension ⋮ Malleable scheduling beyond identical machines ⋮ Parameterized (Approximate) Defective Coloring ⋮ Injective colorings with arithmetic constraints ⋮ Efficient approximation algorithms for bandwidth consecutive multicolorings of graphs ⋮ Approximate strong separation with application in fractional graph coloring and preemptive scheduling. ⋮ Multicoloring trees. ⋮ Unnamed Item ⋮ Approximate minimum sum colorings and maximum \(k\)-colorable subgraphs of chordal graphs ⋮ A competitive analysis for balanced transactional memory workloads ⋮ Approximation algorithms via contraction decomposition ⋮ Radio aggregation scheduling ⋮ Hypercontractivity via tensor calculus ⋮ A Characterization of hard-to-cover CSPs ⋮ Finer Tight Bounds for Coloring on Clique-Width ⋮ Randomly colouring graphs (a combinatorial view) ⋮ A survey on the structure of approximation classes ⋮ Non-clairvoyant scheduling with conflicts for unit-size jobs ⋮ Tight results on minimum entropy set cover ⋮ On percolation and ‐hardness ⋮ Inapproximability and approximability of minimal tree routing and coloring ⋮ Polynomial cases for the vertex coloring problem ⋮ Cross-layer optimization in ultra wideband networks ⋮ Inapproximability results for combinatorial auctions with submodular utility functions ⋮ Clique Clustering Yields a PTAS for max-Coloring Interval Graphs ⋮ Computing the partition function for graph homomorphisms ⋮ On the complexity of bandwidth allocation in radio networks ⋮ On the Lovász theta function and some variants ⋮ New potential functions for greedy independence and coloring ⋮ Fractionally total colouring \(G_{n,p}\) ⋮ Why almost all \(k\)-colorable graphs are easy to color ⋮ Tight approximability results for test set problems in bioinformatics ⋮ A simple algorithm for 4-coloring 3-colorable planar graphs ⋮ On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem ⋮ Semi-Definite positive Programming Relaxations for Graph K_n-Coloring in Frequency Assignment ⋮ On the tractability of coloring semirandom graphs ⋮ Strengthening the Lovász \(\theta(\overline G)\) bound for graph coloring ⋮ Conversion of coloring algorithms into maximum weight independent set algorithms ⋮ New tools and connections for exponential-time approximation ⋮ Exponential-time approximation of weighted set cover ⋮ Unnamed Item ⋮ Clique clustering yields a PTAS for max-coloring interval graphs ⋮ Fractional path coloring in bounded degree trees with applications ⋮ On the recursive largest first algorithm for graph colouring ⋮ Convex Relaxations and Integrality Gaps ⋮ On Injective Colourings of Chordal Graphs ⋮ “Rent-or-Buy” Scheduling and Cost Coloring Problems ⋮ Algorithmic and hardness results for the colorful components problems ⋮ Minimum entropy coloring ⋮ On approximating four covering and packing problems ⋮ Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances ⋮ Hardness of approximate two-level logic minimization and PAC learning with membership queries ⋮ A note on coloring sparse random graphs ⋮ Approximation algorithms in combinatorial scientific computing ⋮ On sum coloring and sum multi-coloring for restricted families of graphs ⋮ Conjunctive query containment revisited ⋮ Priority algorithms for graph optimization problems ⋮ Radiocoloring in planar graphs: Complexity and approximations ⋮ Effective Wireless Scheduling via Hypergraph Sketches ⋮ Unnamed Item ⋮ Minimizing maximum fiber requirement in optical networks ⋮ Heuristics for semirandom graph problems

Cites Work

This page was built for publication: Zero knowledge and the chromatic number