scientific article
From MaRDI portal
Publication:3002782
DOI10.4086/toc.2007.v003a006zbMath1213.68322OpenAlexW2610183793MaRDI QIDQ3002782
Publication date: 24 May 2011
Published in: Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4086/toc.2007.v003a006
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Graph theory (including graph drawing) in computer science (68R10) Random number generation in numerical analysis (65C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Coloring Jacobians revisited: a new algorithm for star and~acyclic bicoloring ⋮ On the Complexity of Finding a Potential Community ⋮ Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis ⋮ A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation ⋮ Local Correlation Breakers and Applications to Three-Source Extractors and Mergers ⋮ Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems ⋮ On the Complexity of the Minimum Independent Set Partition Problem ⋮ Properties of Large 2-Crossing-Critical Graphs ⋮ Approximating maximum diameter-bounded subgraph in unit disk graphs ⋮ Complexity of Coloring Random Graphs ⋮ Approximation and Hardness Results for the Maximum Edges in Transitive Closure Problem ⋮ Distributed minimum vertex coloring and maximum independent set in chordal graphs ⋮ Hardness of Approximate Compaction for Nonplanar Orthogonal Graph Drawings ⋮ THE GRAPH-BIN PACKING PROBLEM ⋮ Token sliding on graphs of girth five ⋮ Extension of some edge graph problems: standard, parameterized and approximation complexity ⋮ Inductive graph invariants and approximation algorithms ⋮ Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank ⋮ Induced odd cycle packing number, independent sets, and chromatic number ⋮ The Complexity of Drawing Graphs on Few Lines and Few Planes ⋮ PTAS for Sparse General-valued CSPs ⋮ Galactic token sliding ⋮ Competitive vertex recoloring. (Online disengagement) ⋮ Approximation schemes for packing problems with \(\ell_p\)-norm diversity constraints ⋮ The complexity of growing a graph ⋮ Repeatedly matching items to agents fairly and efficiently ⋮ Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs ⋮ Star covers and star partitions of double-split graphs ⋮ Token sliding on graphs of girth five ⋮ Extremal independent set reconfiguration ⋮ Improved algorithms for scheduling unsplittable flows on paths ⋮ Every graph is local antimagic total and its applications ⋮ Treewidth versus clique number. II: Tree-independence number ⋮ On local antimagic total labeling of complete graphs amalgamation ⋮ On maximum bipartite matching with separation ⋮ A Modern View on Stability of Approximation ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On streaming algorithms for geometric independent set and clique ⋮ Expander graphs and their applications ⋮ Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs ⋮ From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ Computing the Partition Function of a Polynomial on the Boolean Cube ⋮ On Regularity Lemmas and their Algorithmic Applications ⋮ Fair allocation of indivisible items with conflict graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Covering a Graph with Clubs ⋮ Nonmalleable Extractors and Codes, with Their Many Tampered Extensions ⋮ Approximation Algorithm for the Distance-3 Independent Set Problem on Cubic Graphs ⋮ Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs ⋮ Finer Tight Bounds for Coloring on Clique-Width ⋮ Many disjoint edges in topological graphs ⋮ When polynomial approximation meets exact computation ⋮ Deterministic extractors for small-space sources ⋮ On the Fixed-Parameter Tractability of Some Matching Problems Under the Color-Spanning Model ⋮ Parameterized Complexity of Independent Set in H-Free Graphs. ⋮ Safe Lower Bounds for Graph Coloring ⋮ Election Manipulation on Social Networks: Seeding, Edge Removal, Edge Addition ⋮ A Semi-exact Algorithm for Quickly Computing A Maximum Weight Clique in Large Sparse Graphs ⋮ Restricted Common Superstring and Restricted Common Supersequence ⋮ When polynomial approximation meets exact computation ⋮ In)approximability of Maximum Minimal FVS ⋮ Unnamed Item ⋮ Additive non-approximability of chromatic number in proper minor-closed classes ⋮ Approximability of the independent feedback vertex set problem for bipartite graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Dynamic graph coloring ⋮ Graph orientation with splits ⋮ On the Complexity Landscape of the Domination Chain ⋮ Improved distributed algorithms for coloring interval graphs with application to multicoloring trees ⋮ Convex Relaxations and Integrality Gaps ⋮ On Multi-product Lot-Sizing and Scheduling with Multi-machine Technologies ⋮ Testing for Dense Subsets in a Graph via the Partition Function ⋮ Weighted Upper Edge Cover: Complexity and Approximability ⋮ Overflow management with self-eliminations ⋮ Synchronization problems in automata without non-trivial cycles ⋮ On the tractability of covering a graph with 2-clubs ⋮ Distance-Based Clique Relaxations in Networks: s-Clique and s-Club ⋮ Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs ⋮ Bounded Indistinguishability and the Complexity of Recovering Secrets ⋮ Distance-Preserving Graph Contractions ⋮ Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition ⋮ Probabilistic Automata of Bounded Ambiguity ⋮ On minimizing the makespan when some jobs cannot be assigned on the same machine ⋮ Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking ⋮ Distance-Preserving Graph Contractions ⋮ Improved Dynamic Graph Coloring ⋮ Unnamed Item ⋮ Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure ⋮ A Hierarchy of Standard Polynomial Programming Formulations for the Maximum Clique Problem ⋮ Bayesian agency: linear versus tractable contracts ⋮ On the Nash number and the diminishing Grundy number of a graph ⋮ Algorithmic aspects of broadcast independence ⋮ Traveling salesman problems in temporal graphs ⋮ A fast network-decomposition algorithm and its applications to constant-time distributed computation ⋮ An APTAS for bin packing with clique-graph conflicts ⋮ Independent sets in semi-random hypergraphs ⋮ Moderately exponential time algorithms for the maximum bounded-degree-1 set problem ⋮ Optimal approximation algorithms for maximum distance-bounded subgraph problems ⋮ Approximate generalized matching: \(f\)-matchings and \(f\)-edge covers ⋮ On the complexity of rainbow coloring problems ⋮ Scheduling with complete multipartite incompatibility graph on parallel machines: complexity and algorithms ⋮ Improved approximation algorithms for the spanning star forest problem ⋮ Induced star partition of graphs ⋮ On the \(\Delta \)-interval and the \(\Delta \)-convexity numbers of graphs and graph products ⋮ The maximum independent union of cliques problem: complexity and exact approaches ⋮ Inapproximability results and bounds for the Helly and Radon numbers of a graph ⋮ On the complexity of submap isomorphism and maximum common submap problems ⋮ Domination chain: characterisation, classical complexity, parameterised complexity and approximability ⋮ 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 ⋮ On the \(b\)-continuity of the lexicographic product of graphs ⋮ Comparing multiagent systems research in combinatorial auctions and voting ⋮ Multiprofessor scheduling ⋮ Parameterized approximation via fidelity preserving transformations ⋮ On the approximability of the exemplar adjacency number problem for genomes with gene repetitions ⋮ A framework for parallel second order incremental optimization algorithms for solving partially separable problems ⋮ Efficient approximation algorithms for bandwidth consecutive multicolorings of graphs ⋮ Coalition structure generation: a survey ⋮ A new vertex coloring heuristic and corresponding chromatic number ⋮ A weakly robust PTAS for minimum clique partition in unit disk graphs ⋮ Approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate polynomials ⋮ Computing large independent sets in a single round ⋮ Maximum-weight stable sets and safe lower bounds for graph coloring ⋮ Matchings with lower quotas: algorithms and complexity ⋮ Sparsification and subexponential approximation ⋮ A note on approximating the \(b\)-chromatic number ⋮ PASS approximation: a framework for analyzing and designing heuristics ⋮ Distance-\(d\) independent set problems for bipartite and chordal graphs ⋮ Approximability of constrained LCS ⋮ Restricted assignment scheduling with resource constraints ⋮ Expressive markets for donating to charities ⋮ On the inapproximability of maximum intersection problems ⋮ Bandwidth consecutive multicolorings of graphs ⋮ Approximating independent set in perturbed graphs ⋮ On the \(k\)-edge-incident subgraph problem and its variants ⋮ Graphs with small fall-spectrum ⋮ Bounded max-colorings of graphs ⋮ Regular inference as vertex coloring ⋮ Maximization coloring problems on graphs with few \(P_4\) ⋮ The \textsc{Maximum Colorful Arborescence} problem: how (computationally) hard can it be? ⋮ Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs ⋮ A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees ⋮ Approximation algorithms for intersection graphs ⋮ Minimum clique partition in unit disk graphs ⋮ Complexity of conflict-free colorings of graphs ⋮ Approximability results for the maximum and minimum maximal induced matching problems ⋮ Evader interdiction: algorithms, complexity and collateral damage ⋮ Finding a potential community in networks ⋮ On girth and the parameterized complexity of token sliding and Token Jumping ⋮ Computing inductive vertex orderings ⋮ Computing the partition function for graph homomorphisms ⋮ Stable marriage and roommates problems with restricted edges: complexity and approximability ⋮ Lifted, projected and subgraph-induced inequalities for the representatives \(k\)-fold coloring polytope ⋮ On the complexity of wafer-to-wafer integration ⋮ On two extensions of equimatchable graphs ⋮ On the chromatic number of non-sparse random intersection graphs ⋮ General cut-generating procedures for the stable set polytope ⋮ A branch-and-cut procedure for the Udine course timetabling problem ⋮ In search of the densest subgraph ⋮ Observable graphs ⋮ New results on optimizing rooted triplets consistency ⋮ On the complexity of the independent set problem in triangle graphs ⋮ The complexity of dissociation set problems in graphs ⋮ Top-\(k\) overlapping densest subgraphs: approximation algorithms and computational complexity ⋮ Hardness and tractability of the \(\gamma\)\textsf{-Complete Subgraph} problem ⋮ Algorithmic aspects of upper edge domination ⋮ Combinatorial filter reduction: special cases, approximation, and fixed-parameter tractability ⋮ Approximating the minimum independent dominating set in perturbed graphs ⋮ (In)approximability of maximum minimal FVS ⋮ Minimum entropy coloring ⋮ Probabilistic automata of bounded ambiguity ⋮ On the approximability of the maximum agreement subtree and maximum compatible tree problems ⋮ Extension and its price for the connected vertex cover problem ⋮ Time-communication impossibility results for distributed transactional memory ⋮ Connected greedy coloring of \(H\)-free graphs ⋮ Chromatic numbers of simplicial manifolds ⋮ Parameterized complexity of independent set in H-free graphs ⋮ Computing the \(k\) densest subgraphs of a graph ⋮ Clique partitioning with value-monotone submodular cost ⋮ Additive non-approximability of chromatic number in proper minor-closed classes ⋮ On subexponential and FPT-time inapproximability ⋮ On the average-case complexity of parameterized clique ⋮ Approximability of the upper chromatic number of hypergraphs ⋮ The \(k\)-separator problem: polyhedra, complexity and approximation results ⋮ Some results on more flexible versions of Graph Motif ⋮ Degree-constrained graph orientation: maximum satisfaction and minimum violation ⋮ New limits of treewidth-based tractability in optimization ⋮ Improved approximation for orienting mixed graphs
