- No distributed quantum advantage for approximate graph coloring
2023/07/18 by Xavier Coiteux-Roy, Coiteux-Roy, Xavier, Francesco d’Amore +20 · 2 voices · 6 citations
Computer Science · Mathematics · #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Distributed algorithm #Distributed computing #Distributed systems and fault tolerance #Edge coloring #Graph #Graph coloring #Graph power #Line graph #Matching (statistics) #Mathematics #Omega #Physics #Quantum #Quantum Computing Algorithms and Architecture #Quantum algorithm #Quantum mechanics #Upper and lower bounds
- Breaking the 2ⁿ Barrier for 5-Coloring and 6-Coloring
2020/07/21 by Or Zamir · 1 citation
Computer Science · Engineering · Mathematics · #1-planar graph #Advanced Graph Theory Research #Bounded function #Brooks' theorem #Chordal graph #Chromatic scale #Combinatorics #Complete coloring #Computer science #Degree (music) #Discrete mathematics #Edge coloring #Fractional coloring #Graph #Graph Labeling and Dimension Problems #Graph coloring #Graph power #Greedy coloring #Line graph #List coloring #Mathematics #Physics #Theoretical computer science #graph theory and CDMA systems
- Distributed (Δ +1)-Coloring in Sublogarithmic Rounds
2018/04/12 by David G. Harris, Johannes Schneider, Hsin-Hao Su · 5 citations
Computer Science · Mathematics · #Binary logarithm #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Cryptography and Data Security #Discrete mathematics #Graph #Graph coloring #Log-log plot #Matching (statistics) #Mathematics #Optimization and Search Problems #Randomized algorithm
- Graphs with maximum degree 5 are acyclically 7-colorable
2011/03/24 by Alexandr Kostochka, Christopher Stocker · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #Mathematics #Combinatorics #Degree (music) #Complete coloring #List coloring #Edge coloring #Greedy coloring #Graph #Fractional coloring #Discrete mathematics #Graph coloring #Property (philosophy) #Graph power #Line graph
- How to Draw a Tait-Colorable Graph
2011/01/01 by David A. Richter · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Artificial intelligence #Combinatorics #Computational Geometry and Mesh Generation #Computer graphics (images) #Computer science #Edge coloring #Enhanced Data Rates for GSM Evolution #Geometry #Graph #Graph Labeling and Dimension Problems #Graph coloring #Graph power #Line (geometry) #Line graph #Mathematics
- Computing Tutte Polynomials
2010/09/01 by Gary Haggard, David J. Pearce, Gordon Royle · 1 citation
Mathematics · #Advanced Combinatorial Mathematics #Stochastic processes and statistical mechanics #Markov Chains and Monte Carlo Methods #Tutte polynomial #Chromatic polynomial #Potts model #Combinatorics #Mathematics #Discrete mathematics #Graph coloring #Bracket polynomial #Polynomial #Matrix polynomial #Graph #Voltage graph #Alternating polynomial #Line graph
- Weak graph colorings
2009/08/11 by Fabian Kühn · 1 citation
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Optimization and Search Problems #Advanced Graph Theory Research #Combinatorics #Graph #Edge coloring #Mathematics #Fractional coloring #Graph coloring #Greedy coloring #Complete coloring #Degree (music) #Chromatic scale #Discrete mathematics #List coloring #Binary logarithm #Graph power #Line graph #Physics
- Improved edge-coloring with three colors
2009/05/10 by Łukasz Kowalik · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Edge coloring #Fractional coloring #Graph #Graph Labeling and Dimension Problems #Graph coloring #Graph power #Greedy coloring #Line graph #Mathematics #Time complexity #Vertex (graph theory)
- Computing the Tutte Polynomial in Vertex-Exponential Time
2008/10/01 by Andreas Björklund, Thore Husfeldt, Petteri Kaski +1 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Combinatorial Mathematics #Markov Chains and Monte Carlo Methods #Tutte polynomial #Chromatic polynomial #Combinatorics #Mathematics #Potts model #Discrete mathematics #Time complexity #Graph coloring #Ising model #Voltage graph #Graph #Line graph
- A Note on First-Fit Coloring of Interval Graphs
2008/02/01 by N. S. Narayanaswamy, R. Subhash Babu · 1 citation
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Chordal graph #Clique #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Graph #Graph coloring #Interval (graph theory) #Interval graph #Line graph #Mathematics #Optimization and Search Problems #Pathwidth #Perfect graph #Split graph
- New Linear-Time Algorithms for Edge-Coloring Planar Graphs
2007/10/17 by Richard Cole, Łukasz Kowalik · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Chordal graph #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Degree (music) #Discrete mathematics #Edge coloring #Graph #Graph coloring #Line graph #Mathematics #Optimization and Search Problems #Planar #Planar graph #Theory of computation #Time complexity
- Acyclic coloring of graphs of maximum degree five: Nine colors are enough
2007/09/04 by Guillaume Fertin, André Raspaud · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Brooks' theorem #Chromatic scale #Combinatorics #Complete coloring #Degree (music) #Directed acyclic graph #Discrete mathematics #Edge coloring #Fractional coloring #Graph #Graph Labeling and Dimension Problems #Graph coloring #Graph power #Greedy coloring #Limits and Structures in Graph Theory #Line graph #List coloring #Mathematics
- Improved Exact Algorithms for Counting 3- and 4-Colorings
2007/08/17 by Fedor V. Fomin, Serge Gaspers, Saket Saurabh · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Computer science #Discrete mathematics #Dynamic programming #Graph #Graph Labeling and Dimension Problems #Graph coloring #Mathematics #Optimization and Search Problems #Simple (philosophy) #Theoretical computer science #Time complexity
- Optimal Bitwise Register Allocation Using Integer Linear Programming
2007/06/10 by Rajkishore Barik, Christian Grothoff, Rahul Gupta +2 · 1 citation
Computer Science · #Algorithm #Computer hardware #Computer science #Embedded Systems Design Techniques #Graph #Graph coloring #Integer (computer science) #Integer programming #Interconnection Networks and Systems #Linear programming #Parallel Computing and Optimization Techniques #Parallel computing #Processor register #Programming language #Register (sociolinguistics) #Register allocation #Theoretical computer science
- Landscape analysis of constraint satisfaction problems
2007/02/28 by Florent Krzakala, Florent Krząkała, Jorge Kurchan · 8 citations
Agricultural and Biological Sciences · Computer Science · Mathematics · Physics and Astronomy · #Artificial intelligence #Benchmark (surveying) #Cluster analysis #Combinatorics #Computer science #Constraint (computer-aided design) #Constraint Satisfaction and Optimization #Constraint satisfaction problem #Context (archaeology) #Data Visualization and Analytics #Geography #Geometry #Graph #Graph coloring #Mathematical optimization #Mathematics #Packing problems #Point (geometry) #Sensory Analysis and Statistical Methods #Simple (philosophy) #cond-mat.dis-nn #cond-mat.stat-mech #cs.CC #nlin.CD
- On the Complexity of Register Coalescing
2007/03/01 by Florent Bouchez, Alain Darte, Fabrice Rastello · 1 citation
Computer Science · #Parallel Computing and Optimization Techniques #Optimization and Search Problems #Logic, programming, and type systems #Computer science #Heuristics #Register allocation #Graph #Theoretical computer science #Graph coloring #Parallel computing #Programming language
- Register Allocation: What Does the NP-Completeness Proof of Chaitin et al. Really Prove? Or Revisiting Register Allocation: Why and How
2007/01/01 by Florent Bouchez, Alain Darte, Christophe Guillon +1 · 1 citation
Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Colored #Combinatorics #Completeness (order theory) #Computer science #Discrete mathematics #Graph #Graph coloring #Logic, programming, and type systems #Mathematics #Parallel Computing and Optimization Techniques #Programming language #Register (sociolinguistics) #Register allocation #Theoretical computer science #Time complexity
- Strong edge-coloring of graphs with maximum degree 4 using 22 colors
2006/08/25 by Daniel W. Cranston · 2 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Artificial intelligence #Bounded function #Brooks' theorem #Chordal graph #Combinatorics #Complete coloring #Computer science #Conjecture #Degree (music) #Discrete mathematics #Edge coloring #Enhanced Data Rates for GSM Evolution #Fractional coloring #Graph #Graph Labeling and Dimension Problems #Graph coloring #Graph power #Greedy coloring #Limits and Structures in Graph Theory #Line graph #List coloring #Mathematics #Simple (philosophy) #Simple graph #Upper and lower bounds
- Hybrid Optimizations: Which Optimization Algorithm to Use?
2006/01/01 by John Cavazos, J. Eliot B. Moss, Michael O’Boyle +1 · 3 citations
Computer Science · #Algorithm #Allocator #Compile time #Compiler #Computer science #Formal Methods in Verification #Graph #Graph coloring #Heuristics #Logic, programming, and type systems #Parallel Computing and Optimization Techniques #Parallel computing #Programming language #Register allocation #Theoretical computer science
- Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring
2005/11/15 by Erik D. Demaine, Mohammad Taghi Hajiaghayi, Ken‐ichi Kawarabayashi · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Limits and Structures in Graph Theory #Treewidth #Graph minor #Robertson–Seymour theorem #Graph coloring #Combinatorics #Mathematics #Discrete mathematics #Minor (academic) #1-planar graph #Approximation algorithm #Graph property #Chordal graph #Pathwidth #Voltage graph #Line graph #Graph
- Link scheduling in sensor networks: distributed edge coloring revisited
2005/08/24 by Shashidhar Gandham, Milind Dawande, Ravi Prakash · 1 citation
Computer Science · Engineering · Mathematics · #Energy Efficient Wireless Sensor Networks #Mobile Ad Hoc Networks #Energy Harvesting in Wireless Networks #Time division multiple access #Computer science #Network topology #Scheduling (production processes) #Wireless sensor network #Graph coloring #Enhanced Data Rates for GSM Evolution #Transmission (telecommunications) #Computer network #Topology (electrical circuits) #Algorithm #Graph #Mathematics #Theoretical computer science #Combinatorics #Mathematical optimization #Artificial intelligence #Telecommunications
- A generalized algorithm for graph-coloring register allocation
2004/06/09 by Michael D. Smith, Norman F. Ramsey, Glenn Holloway · 2 citations
Computer Science · Mathematics · #Formal Methods in Verification #Parallel Computing and Optimization Techniques #Embedded Systems Design Techniques #Register allocation #Computer science #Graph coloring #Register (sociolinguistics) #Allocator #Graph #Parallel computing #Register file #Algorithm #Generalization #Programming language #Arithmetic #Theoretical computer science #Compiler #Instruction set #Mathematics
- Small Maximal Independent Sets and Faster Exact Graph Coloring
2003/01/01 by David Eppstein · 2 citations
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Combinatorics #Graph coloring #Mathematics #Graph #Edge coloring #Fractional coloring #Computer science #Discrete mathematics #Graph power #Line graph
- Retargetable Graph-Coloring Register Allocation for Irregular Architectures
2003/01/01 by Johan Runeson, Sven-Olof Nyström · 2 citations
Computer Science · #Algorithm #Compiler #Computer science #Formal Methods in Verification #Graph #Graph coloring #Instruction set #Operating system #Parallel Computing and Optimization Techniques #Parallel computing #Parameterized complexity #Processor register #Programming language #Register (sociolinguistics) #Register allocation #Register file #Retargeting #Software Testing and Debugging Techniques #Theoretical computer science
- Exact Algorithms for NP-Hard Problems: A Survey
2003/01/01 by Gerhard J. Woeginger · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Algorithm #Boolean satisfiability problem #Complexity and Algorithms in Graphs #Computer science #Graph #Graph coloring #Knapsack problem #Mathematical optimization #Mathematics #Satisfiability #Scheduling (production processes) #Theoretical computer science #Travelling salesman problem #Vehicle Routing Optimization Methods
- Broadcast scheduling algorithms for radio networks
2002/11/19 by M.L. Huson, A. Sen · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Interconnection Networks and Systems #Advanced Wireless Network Optimization #Computer science #Transceiver #Scheduling (production processes) #Transmitter #Graph coloring #Algorithm #Radio networks #Distributed computing #Graph #Computer network #Theoretical computer science #Wireless network #Mathematical optimization #Wireless #Telecommunications #Mathematics
- On the computational complexity of strong edge coloring
2002/05/01 by Mohammad Mahdian · 1 citation
Computer Science · Mathematics · Neuroscience · #Advanced Graph Theory Research #Algorithm #Artificial intelligence #Combinatorics #Completeness (order theory) #Computational complexity theory #Computer science #Discrete mathematics #Edge coloring #Enhanced Data Rates for GSM Evolution #Graph #Graph Labeling and Dimension Problems #Graph coloring #Graph power #Line graph #Matching (statistics) #Mathematics #Nuclear Receptors and Signaling #Time complexity
- Linear Scan Register Allocation in the Context of SSA Form and Register Constraints
2002/01/01 by Hanspeter Mössenböck, Michael Pfeiffer · 1 citation
Computer Science · #Algorithm #Allocator #Computer science #Control flow graph #Data flow diagram #Data-flow analysis #Formal Methods in Verification #Graph #Graph coloring #Parallel Computing and Optimization Techniques #Parallel computing #Programming language #Register (sociolinguistics) #Register allocation #Software Testing and Debugging Techniques #Theoretical computer science #x86
- Optimal spilling for CISC machines with few registers
2001/05/01 by Andrew W. Appel, Lal George · 9 citations
Computer Science · Mathematics · #Parallel Computing and Optimization Techniques #Interconnection Networks and Systems #Complexity and Algorithms in Graphs #Register allocation #Computer science #Heuristics #Register (sociolinguistics) #Parallel computing #Iterated function #Processor register #Pentium #Graph coloring #Integer programming #Code (set theory) #Algorithm #Graph #Theoretical computer science #Mathematics #Programming language #Compiler #Operating system
- An O(n2) algorithm to color Meyniel graphs
2001/05/01 by F. Roussel, Irena Rusu, I. Rusu · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Algorithm #Combinatorics #Discrete mathematics #Edge coloring #Graph #Graph Labeling and Dimension Problems #Graph coloring #Graph power #Greedy coloring #Line graph #Mathematics #graph theory and CDMA systems
more