The interval count of interval graphs and orders: a short survey
---
paper_title: Computation Structures

paper_content:

From the Publisher: ::: Computation Structures integrates thorough coverage of digital logic design with a comprehensive presentation of computer architecture. It contains a wealth of information for anyone who designs computers or works with computer systems. Indeed, the authors' goal is to teach people to look at systems, as a whole, without being bound by the artificial interfaces that are often used to train specialist engineers. Ward and Halstead demystify the construction of computing hardware by illustrating how it is built up from digital circuits through higher-level components to processors and memories and emphasizing how the design of hardware is affected by its intended use. The book is firmly based in the real world, with pertinent discussions of the many trade-off decisions practicing engineers must confront. Throughout the book, the authors use the running example of the MAYBE computer--a simple microarchitecture that readers can construct and operate--to establish connections between theory and real-world practice. Among the topics addressed are the digital abstracts; combinatorial devices and circuits; the synthesis of digital systems; finite-state machines; control structures and disciplines; performance measures and trade-offs; communication; interpretation; microinterpreter architectures; microprogramming; single-sequence machines; stack, register, and memory architectures; RISC machines; processes; interrupts and priorities; and architectural horizons.
---
paper_title: Reasoning about Plans

paper_content:

Temporal Reasoning and Planning 1.1 Introduction 1.1.1 Background: Actions as State Change 1.1.2 Temporally Explicit Representations 1.2 Representing Time 1.2.1 Temporal Logic 1.3 The Logic of Action 1.4 The Logic for Planning 1.4.1 Predicting the Future 1.4.2 Planning With a Temporal World Model 1.5 The Planning System 1.5.1 A Nonlinear Planning Algorithm 1.5.2 Assumptions About Temporal Extension 1.5.3 Discussion of the Algorithm 1.6 The Door-Latch Problem 1.7 Hierarchical Planning 1.8 Conclusions A Formal Theory of Plan Recognition and its Implementation Henry A. Kautz 2.1 Introduction 2.1.1 Background 2.1.2 Overview 2.1.3 Plan Recognition and the Frame Problem 2.2 Representing Event Hierarchies 2.2.1 The Language 2.2.2 Representation of Time, Properties, and Events 2.2.3 The Event Hierarchy 2.2.4 Example: The Cooking World 2.3 The Formal Theory of Recognition 2.3.1 Exhaustiveness Assumptions (EXA) 2.3.2 Disjointness Assumptions (DJA) 2.3.3 Component/Use Assumptions (CUA) 2.3.4 Minimum Cardinality Assumptions (MCA) 2.3.5 Example: the Cooking World 2.3.6 Circumscription and Plan Recognition 2.4 Examples 2.4.1 An Operating System 2.4.2 Medical Diagnosis 2.5 Algorithms for Plan Recognition 2.5.1 Directing Inference 2.5.2 Explanation Graphs 2.5.3 Implementing Component/Use Assumptions 2.5.4 Constraint Checking 2.5.5 Algorithms Planning With Simultaneous Actions and External Events Richard N. Pelavin 3.1 Introduction 3.1.1 Key Considerations 3.1.2 Overview 3.2 Representations That Treat Simultaneous Events 3.2.1 Interval Logic 3.2.2 A Model Based on Events 3.2.3 Branching time Models 3.2.4 Adapting the State-Change Model to Handle Simultaneous Events 3.3 The Semantic Model 3.3.1 The Interval Logic Structure 3.3.2 The Branching Time Structure 3.3.3 Plan Instances and Basic Actions 3.3.4 The Closeness Function 3.3.5 Composition and Interaction of Basic Action Instances 3.4 The Language 3.4.1 The Syntax: Additions to Interval Logic 3.4.2 Interpretations 3.5 Planning 3.5.1 Planner Correctness 3.5.2 The World Description 3.5.3 The Action Specifications 3.5.4 Plan Instance Composition 3.5.5 Persistence and Maintenance Plan Instances 3.6 A Planning Algorithm 3.6.1 The Input to the Planning Algorithm 3.6.2 The Algorithm 3.6.3 Planning Examples 3.6.4 Limitations of the Planning Algorithm 3.7 Discussion 3.7.1 Issues Outside the Scope of the Deductive Logic 3.7.2 Incomplete Descriptions and Obtaining Additional Information 3.7.3 Planning With an Incorrect World Description 3.7.4 Addressing the Frame Problem 3.8 Appendix A. the Semantic Model and Logical Language 3.8.1 The Semantic Model 3.8.2 The Syntax 3.8.3 The Interpretation of the Language 3.9 Appendix B. Proof Theory Abstraction in Planning Josh D. Tenenberg 4.1 Introduction 4.1.1 Inheritance Abstraction 4.1.2 Relaxed Model Abstraction 4.1.3 Macro Expansion 4.1.4 Outline 4.1.5 STRIPS 4.2 Inheritance Abstraction 4.2.1 Generalizing Inheritance 4.2.2 Predicate Mappings 4.2.3 Model Abstraction 4.2.4 Theory Abstraction 4.2.5 Theory Mappings 4.2.6 Proof-Theoretic Relationship Between Levels 4.2.7 Abstract STRIPS Systems 4.2.8 Downward Solution Property 4.2.9 Example 4.2.10 The Frame Problem 4.2.11 Comparison With Kautz 4.2.12 Related Research in Plan Generation 4.2.13 Summary 4.3 Abstraction Using Relaxed Models 4.3.1 ABSTRIPS 4.3.2 Planning With Inconsistent Systems 4.3.3 Restricted ABSTRIPS 4.3.4 Simple Restrictions 4.3.5 Relaxing the Simple Restrictions 4.3.6 Example 4.3.7 Upward Solution Property 4.3.8 The Monotonicity Property 4.3.9 Search 4.3.10 Related Research 4.3.11 Summary 4.4 Conclusion 4.4.1 Discrete Levels 4.4.2 Solution Properties 4.5 Proofs 4.5.1 Proofs for Inheritance Abstraction 4.5.2 Proofs for Relaxed Model Abstraction References Index
---
paper_title: Temporally Distributed Symptoms In Technical Diagnosis

paper_content:

Related work.- Temporal matching.- Incorporating TDSs into existing diagnostic paradigms.- Conclusion.
---
paper_title: Realizing Interval Graphs With Size And Distance Constraints

paper_content:

We study the following problem: given an interval graph, does it have a realization which satisfies additional constraints on the distances between interval endpoints? This problem arises in numerous applications in which topological information on intersection of pairs of intervals is accompanied by additional metric information on their order, distance, or size. An important application is physical mapping, a central challenge in the human genome project. Our results are (1) a polynomial algorithm for the problem on interval graphs which admit a unique clique order (UCO graphs). This class of graphs properly contains all prime interval graphs. (2) In case all constraints are upper and lower bounds on individual interval lengths, the problem on UCO graphs is linearly equivalent to deciding if a system of difference inequalities is feasible. (3) Even if all the constraints are prescribed lengths of individual intervals, the problem is NP-complete. Hence, problems (1) and (2) are also NP-complete on arbitrary interval graphs.
---
paper_title: The Interval Count of a Graph

paper_content:

The interval count of an interval graph G is the minimum number of different interval sizes needed to represent the vertices of G, where two vertices are adjacent if and only if their intervals intersect.We show that if G is an interval graph and for some vertex x, $G - \{ x \}$ has interval count one, then G has interval count two or less.We also show how to construct examples of interval graphs where the interval count of G exceeds that of $G - \{ x \}$ by at least two when the latter number is two or more.
---
paper_title: Maintaining knowledge about temporal intervals

paper_content:

An interval-based temporal logic is introduced, together with a computationally effective reasoning algorithm based on constraint propagation. This system is notable in offering a delicate balance between
---
paper_title: Chronological orderings of interval graphs

paper_content:

Abstract If an undirected graph is the intersection graph of a set of intervals of the real line, it is called an interval graph and the set of intervals is called an interval representation of the graph. An interval graph typically has many representations that differ in the order of the endpoints of the intervals along the line. This paper gives three methods for describing these differences and shows how these methods can be used to determine whether a graph has a representation satisfying various restrictions on the relative positions of the intervals. It concludes with an application of these results to the subject of interval counts of interval graphs.
---
paper_title: Chronological orderings of interval graphs

paper_content:

Abstract If an undirected graph is the intersection graph of a set of intervals of the real line, it is called an interval graph and the set of intervals is called an interval representation of the graph. An interval graph typically has many representations that differ in the order of the endpoints of the intervals along the line. This paper gives three methods for describing these differences and shows how these methods can be used to determine whether a graph has a representation satisfying various restrictions on the relative positions of the intervals. It concludes with an application of these results to the subject of interval counts of interval graphs.
---
paper_title: The Interval Count of a Graph

paper_content:

The interval count of an interval graph G is the minimum number of different interval sizes needed to represent the vertices of G, where two vertices are adjacent if and only if their intervals intersect.We show that if G is an interval graph and for some vertex x, $G - \{ x \}$ has interval count one, then G has interval count two or less.We also show how to construct examples of interval graphs where the interval count of G exceeds that of $G - \{ x \}$ by at least two when the latter number is two or more.
---
paper_title: On counting interval lengths of interval graphs

paper_content:

Given an interval graph G, the interval count problem is that of computing the minimum number IC(G) of interval lengths needed to represent G. Although the problem of deciding whether IC(G)=1 is equivalent to that of recognizing unit-interval graphs, which is a well-known problem having several efficient recognition approaches, very little is known about deciding efficiently whether IC(G)=k for fixed k>=2. We provide efficient computations of the interval count of generalizations of threshold graphs.
---
paper_title: Characterizing Intersection Graphs of Substars of a Star.

paper_content:

With end-to-end electrolytic cells, in particular cells for producing aluminum, high investment and operating costs are incurred by the arrangement of the busbars outside the cell. The magnetic fields produced by the busbars give rise to streaming of the metal in the cell. By providing direct connections between the individual anodes and the electrically connected busbars running along the side of the cell, in a plane just above the anodes, the costs are lowered and the harmful effects of the magnetic fields diminished. A further effect countering the magnetic forces created by the busbars can be achieved by an asymmetric arrangement in which the busbars are at different distances from the cathode bar ends or by connecting an unequal number of cathode bar ends to busbars on opposite sides of the longitudinal axis of the cell.
---
paper_title: Realizing Interval Graphs With Size And Distance Constraints

paper_content:

We study the following problem: given an interval graph, does it have a realization which satisfies additional constraints on the distances between interval endpoints? This problem arises in numerous applications in which topological information on intersection of pairs of intervals is accompanied by additional metric information on their order, distance, or size. An important application is physical mapping, a central challenge in the human genome project. Our results are (1) a polynomial algorithm for the problem on interval graphs which admit a unique clique order (UCO graphs). This class of graphs properly contains all prime interval graphs. (2) In case all constraints are upper and lower bounds on individual interval lengths, the problem on UCO graphs is linearly equivalent to deciding if a system of difference inequalities is feasible. (3) Even if all the constraints are prescribed lengths of individual intervals, the problem is NP-complete. Hence, problems (1) and (2) are also NP-complete on arbitrary interval graphs.
---
paper_title: On counting interval lengths of interval graphs

paper_content:

Given an interval graph G, the interval count problem is that of computing the minimum number IC(G) of interval lengths needed to represent G. Although the problem of deciding whether IC(G)=1 is equivalent to that of recognizing unit-interval graphs, which is a well-known problem having several efficient recognition approaches, very little is known about deciding efficiently whether IC(G)=k for fixed k>=2. We provide efficient computations of the interval count of generalizations of threshold graphs.
---

Title: The Interval Count of Interval Graphs and Orders: A Short Survey

Section 1: Interval Count One
Description 1: This section explores the problem of determining whether an interval graph has an interval count of one, equivalent to recognizing unit interval graphs, and presents theorems and characterizations related to this question.

Section 2: Interval Count Two
Description 2: This section discusses the problem of determining if a graph or order has an interval count of two, including work on the conditions and characterizations of such graphs and orders, and provides relevant theorems and conjectures. 

Section 3: Arbitrary Interval Count
Description 3: This section examines the complexity and characterization of graphs and orders with arbitrary interval count values, discussing forbidden subgraphs and suborders as well as general conjectures and results regarding interval counts.

Section 4: Interval Count of Subclasses of Graphs and Orders
Description 4: This section presents results for the interval count problem restricted to specific subclasses of interval graphs and orders, detailing particular types of graphs like starlike-threshold, trivially perfect, generalized-threshold, and extended-bull-free graphs.

Section 5: Related Problems
Description 5: This section addresses related problems that involve interval lengths but do not focus on the minimization of their number, including constraints on interval lengths and distances between interval extreme points in interval models.

Section 6: Concluding Remarks
Description 6: This section summarizes the main findings regarding interval counts, discusses the status of known results, open problems, and the importance of studying the interval count problem for interval graphs and orders.