An exponential time 2-approximation algorithm for bandwidth (Q392018): Difference between revisions

@@ Property / cites work @@
+Counting Subgraphs via Homomorphisms
@@ Property / cites work: Counting Subgraphs via Homomorphisms / rank @@
+Normal rank
@@ Property / cites work @@
+The Bandwidth of Caterpillars with Hairs of Length 1 and 2
+Normal rank
@@ Property / cites work @@
+Set Partitioning via Inclusion-Exclusion
@@ Property / cites work: Set Partitioning via Inclusion-Exclusion / rank @@
+Normal rank
@@ Property / cites work @@
+Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems
+Normal rank
@@ Property / cites work @@
+Beyond <i>NP</i>-completeness for problems of bounded width (extended abstract)
+Normal rank
@@ Property / cites work @@
+Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
+Normal rank
@@ Property / cites work @@
+Approximation of min coloring by moderately exponential algorithms
+Normal rank
@@ Property / cites work @@
+Efficient approximation of Min Set Cover by moderately exponential algorithms
+Normal rank
@@ Property / cites work @@
+Approximating the max-edge-coloring problem
@@ Property / cites work: Approximating the max-edge-coloring problem / rank @@
+Normal rank
@@ Property / cites work @@
+Fixed-parameter approximation: conceptual framework and approximability results
+Normal rank
@@ Property / cites work @@
+On Parameterized Approximability
@@ Property / cites work: On Parameterized Approximability / rank @@
+Normal rank
@@ Property / cites work @@
+Linear FPT reductions and computational lower bounds
+Normal rank
@@ Property / cites work @@
+Exponential-time approximation of weighted set cover
+Normal rank
@@ Property / cites work @@
+Bandwidth and distortion revisited
@@ Property / cites work: Bandwidth and distortion revisited / rank @@
+Normal rank
@@ Property / cites work @@
+Even Faster Exact Bandwidth
@@ Property / cites work: Even Faster Exact Bandwidth / rank @@
+Normal rank
@@ Property / cites work @@
+Exact and approximate bandwidth
@@ Property / cites work: Exact and approximate bandwidth / rank @@
+Normal rank
@@ Property / cites work @@
+MAX SAT approximation beyond the limits of polynomial-time approximation
+Normal rank
@@ Property / cites work @@
+Parameterized Approximation Problems
@@ Property / cites work: Parameterized Approximation Problems / rank @@
+Normal rank
@@ Property / cites work @@
+Q4780797
@@ Property / cites work: Q4780797 / rank @@
+Normal rank
@@ Property / cites work @@
+A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem
+Normal rank
@@ Property / cites work @@
+Approximating the bandwidth via volume respecting embeddings
+Normal rank
@@ Property / cites work @@
+Q2721963
@@ Property / cites work: Q2721963 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximating the bandwidth of caterpillars
@@ Property / cites work: Approximating the bandwidth of caterpillars / rank @@
+Normal rank
@@ Property / cites work @@
+An Exponential Time 2-Approximation Algorithm for Bandwidth
+Normal rank
@@ Property / cites work @@
+Complexity Results for Bandwidth Minimization
@@ Property / cites work: Complexity Results for Bandwidth Minimization / rank @@
+Normal rank
@@ Property / cites work @@
+Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
+Normal rank
@@ Property / cites work @@
+Bandwidth of bipartite permutation graphs in polynomial time
+Normal rank
@@ Property / cites work @@
+Worst-case study of local search for MAX-\(k\)-SAT.
+Normal rank
@@ Property / cites work @@
+On the complexity of \(k\)-SAT
@@ Property / cites work: On the complexity of \(k\)-SAT / rank @@
+Normal rank
@@ Property / cites work @@
+A mildly exponential approximation algorithm for the permanent
+Normal rank
@@ Property / cites work @@
+Volume distortion for subsets of Euclidean spaces
@@ Property / cites work: Volume distortion for subsets of Euclidean spaces / rank @@
+Normal rank
@@ Property / cites work @@
+Computing the Bandwidth of Interval Graphs
@@ Property / cites work: Computing the Bandwidth of Interval Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Approximating the Bandwidth for Asteroidal Triple-Free Graphs
+Normal rank
@@ Property / cites work @@
+Bandwidth of chain graphs
@@ Property / cites work: Bandwidth of chain graphs / rank @@
+Normal rank
@@ Property / cites work @@
+On finding the minimum bandwidth of interval graphs
+Normal rank
@@ Property / cites work @@
+The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
+Normal rank
@@ Property / cites work @@
+The NP-completeness of the bandwidth minimization problem
+Normal rank
@@ Property / cites work @@
+Efficient exact algorithms through enumerating maximal independent sets and other techniques
+Normal rank
@@ Property / cites work @@
+Bandwidth of Convex Bipartite Graphs and Related Graphs
+Normal rank
@@ Property / cites work @@
+An $O( n \log n )$ Algorithm for Bandwidth of Interval Graphs
+Normal rank
@@ Property / cites work @@
+Confronting hardness using a hybrid approach
@@ Property / cites work: Confronting hardness using a hybrid approach / rank @@
+Normal rank
@@ Property / cites work @@
+Q3839788
@@ Property / cites work: Q3839788 / rank @@
+Normal rank