Interval graph representation with given interval and intersection lengths
From MaRDI portal
Publication:491160
DOI10.1016/j.jda.2015.05.011zbMath1336.05134OpenAlexW1624107519MaRDI QIDQ491160
Johannes Köbler, Sebastian Kuhnert, Osamu Watanabe
Publication date: 24 August 2015
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2015.05.011
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items
Dimension of restricted classes of interval orders ⋮ Parameterized complexity of perfectly matched sets ⋮ Stick graphs with length constraints ⋮ Recognizing Stick Graphs with and without Length Constraints ⋮ Overlaying a hypergraph with a graph with bounded maximum degree ⋮ On the isomorphism problem for Helly circular-arc graphs
Cites Work
- Unnamed Item
- Maintaining knowledge about temporal intervals
- Extending partial representations of proper and unit interval graphs
- On the calculation of transitive reduction-closure of orders
- Chronological orderings of interval graphs
- The method of forced enumeration for nondeterministic automata
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Linear-time recognition of circular-arc graphs
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- Algorithmic graph theory and perfect graphs
- Incidence matrices and interval graphs
- Extending partial representations of interval graphs
- A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs
- Helly Circular-Arc Graph Isomorphism Is in Logspace
- Bounded Representations of Interval and Proper Interval Graphs
- The LBFS Structure and Recognition of Interval Graphs
- Simultaneous Interval Graphs
- Interval Graphs: Canonical Representations in Logspace
- Reasoning about temporal relations
- Undirected connectivity in log-space
- Nondeterministic Space is Closed under Complementation
- Fast and Simple Algorithms for Recognizing Chordal Comparability Graphs and Interval Graphs
- Realizing Interval Graphs with Size and Distance Constraints
- Constraint Satisfaction Problems on Intervals and Lengths
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
- Efficient Parallel Algorithms for Chordal Graphs
- Disconnectivity and Relative Positions in Simultaneous Embeddings
