Interval graphs and related topics
From MaRDI portal
Publication:1060229
DOI10.1016/0012-365X(85)90039-1zbMath0568.05046MaRDI QIDQ1060229
Publication date: 1985
Published in: Discrete Mathematics (Search for Journal in Brave)
Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Graph theory (05C99)
Related Items
Computing the jump number on semi-orders is polynomial ⋮ A special planar satisfiability problem and a consequence of its NP- completeness ⋮ New linear time algorithms for generating perfect elimination orderings of chordal graphs ⋮ Paired domination on interval and circular-arc graphs ⋮ Intersection graphs of halflines and halfplanes ⋮ Representing digraphs using intervals or circular arcs ⋮ Recognizing and representing proper interval graphs in parallel using merging and sorting ⋮ Succinct encodings for families of interval graphs ⋮ An 0(n log n\(+m\,\log \,\log \,n)\) maximum weight clique algorithm for circular-arc graphs ⋮ The \(p\)-Maxian problem on interval graphs ⋮ Satisfiability problems on intervals and unit intervals ⋮ Preference structures and threshold models ⋮ Parallel interval order recognition and construction of interval representations ⋮ Locally definable vertex set properties are efficiently enumerable ⋮ Block matrix models for dynamic networks ⋮ Difference graphs ⋮ Counting endpoint sequences for interval orders and interval graphs ⋮ Paths in interval graphs and circular arc graphs ⋮ Characterization of the graphs with boxicity \(\leq 2\) ⋮ Succinct navigational oracles for families of intersection graphs on a circle ⋮ Completeness for intersection classes ⋮ Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs ⋮ Set graphs. III: Proof pearl: Claw-free graphs mirrored into transitive hereditarily finite sets
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Space graphs and sphericity
- Some results about the interval number of a graph
- On the sphericity and cubicity of graphs
- The edge intersection graphs of paths in a tree
- Chronological orderings of interval graphs
- On the sphericity for the join of many graphs
- Tolerance graphs
- Some remarks on interval graphs
- Interval graphs and searching
- An O(qn) algorithm to q-color a proper family of circular arcs
- Edge and vertex intersection of paths in a tree
- On the chromatic number of multiple interval graphs and overlap graphs
- Covering and coloring problems for relatives of intervals
- Triangulated edge intersection graphs of paths in a tree
- Decomposition by clique separators
- Split graphs of Dilworth number 2
- A note on the interval number of a graph
- Irrepresentability by multiple intersection, or why the interval number is unbounded
- Homogeneously representable interval graphs
- Characterizing intersection classes of graphs
- On minimal augmentation of a graph to obtain an interval graph
- Optimal packing and covering in the plane are NP-complete
- An application of vertex packing to data analysis in the evaluation of pavement deterioration
- The asymptotic probability that a random graph is a unit interval graph, indifference graph, or proper interval graph
- Comparability graphs and intersection graphs
- Partitionable graphs, circle graphs, and the Berge strong perfect graph conjecture
- A characterisation of rigid circuit graphs
- Betweenness, orders and interval graphs
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- On the Desirability of Acyclic Database Schemes
- Degrees of acyclicity for hypergraphs and relational database schemes
- Syntactic Characterization of Tree Database Schemas
- On the 2-Dimensional Channel Assignment Problem
- Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Optimal algorithms to compute the closure of a set of iso-rectangles
- An optimal contour algorithm for iso-oriented rectangles
- Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
- The Complexity of the Partial Order Dimension Problem
- Counting Interval Graphs
- Using Semi-Joins to Solve Relational Queries
- Segments, rectangles, contours
- Power of Natural Semijoins
- Rectilinear line segment intersection, layered segment trees, and dynamization
- The measure problem for rectangular ranges in d-space
- An improved algorithm for the rectangle enclosure problem
- A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs
- An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs
- Partially Ordered Sets
- Corrigendum
