Interval graph representation with given interval and intersection lengths
DOI10.1016/J.JDA.2015.05.011zbMATH Open1336.05134OpenAlexW1624107519MaRDI QIDQ491160FDOQ491160
Authors: 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
Recommendations
- Interval graph representation with given interval and intersection lengths
- Recognizing graphs with fixed interval number is NP-complete
- Realizing Interval Graphs with Size and Distance Constraints
- Interval graphs: canonical representations in logspace
- Interval graphs: canonical representation in logspace
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph representations (geometric and intersection representations, etc.) (05C62)
Cites Work
- Network flows. Theory, algorithms, and applications.
- Maintaining knowledge about temporal intervals
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Linear-time recognition of circular-arc graphs
- Algorithmic graph theory and perfect graphs
- Incidence matrices and interval graphs
- Helly circular-arc graph isomorphism is in logspace
- Interval graphs: canonical representations in logspace
- Undirected connectivity in log-space
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
- Reasoning about temporal relations, the tractable subalgebras of Allen's interval algebra
- Nondeterministic Space is Closed under Complementation
- Constraint Satisfaction Problems on Intervals and Lengths
- The method of forced enumeration for nondeterministic automata
- On the calculation of transitive reduction-closure of orders
- Simultaneous interval graphs
- The LBFS structure and recognition of interval graphs
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- A Fully dynamic algorithm for recognizing and representing proper interval graphs
- Chronological orderings of interval graphs
- Fast and Simple Algorithms for Recognizing Chordal Comparability Graphs and Interval Graphs
- Bounded representations of interval and proper interval graphs
- Realizing Interval Graphs with Size and Distance Constraints
- Efficient Parallel Algorithms for Chordal Graphs
- Disconnectivity and relative positions in simultaneous embeddings
Cited In (15)
- On the isomorphism problem for Helly circular-arc graphs
- Recognizing graphs with fixed interval number is NP-complete
- Graphs of interval count two with a given partition
- FO model checking of interval graphs
- FO model checking of interval graphs
- Interval graph representation with given interval and intersection lengths
- Stick graphs with length constraints
- Recognizing stick graphs with and without length constraints
- On interval graphs and matrice profiles
- Overlaying a hypergraph with a graph with bounded maximum degree
- Interval graphs with side (and size) constraints
- Parameterized complexity of perfectly matched sets
- A graph-theoretic barcode ordering model for linked-reads
- Dimension of restricted classes of interval orders
- Interval graphs: canonical representation in logspace
This page was built for publication: Interval graph representation with given interval and intersection lengths
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q491160)
