↓ Skip to main content

Computing and Combinatorics

Overview of attention for book
Cover of 'Computing and Combinatorics'

Table of Contents

  1. Altmetric Badge
    Book Overview
  2. Altmetric Badge
    Chapter 1 Complete Problems for Valiant’s Class of qp-Computable Families of Polynomials
  3. Altmetric Badge
    Chapter 2 Log-Space Constructible Universal Traversal Sequences for Cycles of Length O(n 4.03)
  4. Altmetric Badge
    Chapter 3 On Universally Polynomial Context-Free Languages
  5. Altmetric Badge
    Chapter 4 Separating Oblivious and Non-oblivious BPs
  6. Altmetric Badge
    Chapter 5 Program Schemes, Queues, the Recursive Spectrum and Zero-One Laws
  7. Altmetric Badge
    Chapter 6 Algebraic Properties for P-Selectivity
  8. Altmetric Badge
    Chapter 7 Parallelizability of Some P-Complete Geometric Problems in the EREW-PRAM
  9. Altmetric Badge
    Chapter 8 Enhanced Sequence Reconstruction with DNA Microarray Application
  10. Altmetric Badge
    Chapter 9 Non-approximability of Weighted Multiple Sequence Alignment
  11. Altmetric Badge
    Chapter 10 A Greedy Algorithm for Optimal Recombination
  12. Altmetric Badge
    Chapter 11 Generating Well-Shaped d-dimensional Delaunay Meshes
  13. Altmetric Badge
    Chapter 12 Towards Compatible Triangulations
  14. Altmetric Badge
    Chapter 13 An Improved Upper Bound on the Size of Planar Convex-Hulls
  15. Altmetric Badge
    Chapter 14 On the Planar Two-Watchtower Problem
  16. Altmetric Badge
    Chapter 15 Efficient Generation of Triconnected Plane Triangulations
  17. Altmetric Badge
    Chapter 16 Packing Two Disks into a Polygonal Environment
  18. Altmetric Badge
    Chapter 17 Maximum Red/Blue Interval Matching with Application
  19. Altmetric Badge
    Chapter 18 Computing Farthest Neighbors on a Convex Polytope
  20. Altmetric Badge
    Chapter 19 Finding an Optimal Bridge between Two Polygons
  21. Altmetric Badge
    Chapter 20 How Good Is Sink Insertion?
  22. Altmetric Badge
    Chapter 21 Polynomial Time Algorithms for Three-Label Point Labeling
  23. Altmetric Badge
    Chapter 22 Approximation Algorithms for the Watchman Route and Zookeeper’s Problems
  24. Altmetric Badge
    Chapter 23 PC-Trees vs. PQ-Trees
  25. Altmetric Badge
    Chapter 24 Stacks versus Deques
  26. Altmetric Badge
    Chapter 25 Optimizing a Computational Method for Length Lower Bounds for Reflecting Sequences
  27. Altmetric Badge
    Chapter 26 Competitive Facility Location along a Highway
  28. Altmetric Badge
    Chapter 27 Membership for Core of LP Games and Other Games
  29. Altmetric Badge
    Chapter 28 Strong Solutions to the Identification Problem
  30. Altmetric Badge
    Chapter 29 Area Efficient Exponentiation Using Modular Multiplier/Squarer in GF(2m)1
  31. Altmetric Badge
    Chapter 30 A Space Saving Trick for Directed Dynamic Transitive Closure and Shortest Path Algorithms
  32. Altmetric Badge
    Chapter 31 Finding the Most Vital Node of a Shortest Path
  33. Altmetric Badge
    Chapter 32 Algorithm for the Cost Edge-Coloring of Trees
  34. Altmetric Badge
    Chapter 33 Counting H-Colorings of Partial k-Trees
  35. Altmetric Badge
    Chapter 34 A Linear Time Algorithm for Enumerating All the Minimum and Minimal Separators of a Chordal Graph
  36. Altmetric Badge
    Chapter 35 Graph Separators: A Parameterized View
  37. Altmetric Badge
    Chapter 36 On Assigning Prefix Free Codes to the Vertices of a Graph
  38. Altmetric Badge
    Chapter 37 A New Measure of Edit Distance between Labeled Trees
  39. Altmetric Badge
    Chapter 38 A Highly Efficient Algorithm to Determine Bicritical Graphs
  40. Altmetric Badge
    Chapter 39 Layered Drawings of Graphs with Crossing Constraints
  41. Altmetric Badge
    Chapter 40 On the Validity of Hierarchical Decompositions
  42. Altmetric Badge
    Chapter 41 Lower Bounds on the Minus Domination and k-Subdomination Numbers
  43. Altmetric Badge
    Chapter 42 Edge Connectivity vs Vertex Connectivity in Chordal Graphs
  44. Altmetric Badge
    Chapter 43 Changing the Diameter of Graph Products
  45. Altmetric Badge
    Chapter 44 Plane Graphs with Acyclic Complex
  46. Altmetric Badge
    Chapter 45 On the Domination Numbers of Generalized de Bruijn Digraphs and Generalized Kautz Digraphs
  47. Altmetric Badge
    Chapter 46 A Notion of Cross-Perfect Bipartite Graphs
  48. Altmetric Badge
    Chapter 47 Some Results on Orthogonal Factorizations
  49. Altmetric Badge
    Chapter 48 Cluttered Orderings for the Complete Graph
  50. Altmetric Badge
    Chapter 49 Improved On-Line Stream Merging: From a Restricted to a General Setting
  51. Altmetric Badge
    Chapter 50 On-Line Deadline Scheduling on Multiple Resources
  52. Altmetric Badge
    Chapter 51 Competitive Online Scheduling with Level of Service
  53. Altmetric Badge
    Chapter 52 On-Line Variable Sized Covering
  54. Altmetric Badge
    Chapter 53 On Testing for Zero Polynomials by a Set of Points with Bounded Precision
  55. Altmetric Badge
    Chapter 54 A Randomized Algorithm for Gossiping in Radio Networks
  56. Altmetric Badge
    Chapter 55 Deterministic Application of Grover’s Quantum Search Algorithm
  57. Altmetric Badge
    Chapter 56 Random Instance Generation for MAX 3SAT
  58. Altmetric Badge
    Chapter 57 The Euclidean Bottleneck Steiner Tree and Steiner Tree with Minimum Number of Steiner Points
  59. Altmetric Badge
    Chapter 58 AnFPTAS forWeight-Constrained SteinerTrees in Series-Parallel Graphs
  60. Altmetric Badge
    Chapter 59 Decidable Approximations on Generalized and Parameterized Discrete Timed Automata
  61. Altmetric Badge
    Chapter 60 Multiplicative Adaptive Algorithms for User Preference Retrieval
  62. Altmetric Badge
    Chapter 61 Parametric Scheduling for Network Constraints
  63. Altmetric Badge
    Chapter 62 A Logical Framework for Knowledge Sharing in Multi-agent Systems
  64. Altmetric Badge
    Chapter 63 A Lockout Avoidance Algorithm without Using Time-Stamps for the k-Exclusion Problem
  65. Altmetric Badge
    Chapter 64 Prefix-Free Languages and Initial Segments of Computably Enumerable Degrees
  66. Altmetric Badge
    Chapter 65 Weakly Computable Real Numbers and Total Computable Real Functions
  67. Altmetric Badge
    Chapter 66 Turing Computability of a Nonlinear Schrödinger Propagator
Attention for Chapter 4: Separating Oblivious and Non-oblivious BPs
Altmetric Badge

Citations

dimensions_citation
1 Dimensions
You are seeing a free-to-access but limited selection of the activity Altmetric has collected about this research output. Click here to find out more.
Chapter title
Separating Oblivious and Non-oblivious BPs
Chapter number 4
Book title
Computing and Combinatorics
Published by
Springer, Berlin, Heidelberg, August 2001
DOI 10.1007/3-540-44679-6_4
Book ISBNs
978-3-54-042494-9, 978-3-54-044679-8
Authors

Kazuo Iwama, Yasuo Okabe, Toshiro Takase