Interval graph representation with given interval and intersection lengths

DOI10.1016/J.JDA.2015.05.011MaRDI QIDQ491160zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

intersection graphinterval graphlinear timelogspaceconstrained graph representation

Mathematics Subject Classification ID

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)

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

Cites work

• A Fully dynamic algorithm for recognizing and representing proper interval graphs
• Algorithmic graph theory and perfect graphs
• Bounded representations of interval and proper interval graphs
• Chronological orderings of interval graphs
• Constraint Satisfaction Problems on Intervals and Lengths
• Disconnectivity and relative positions in simultaneous embeddings
• Efficient Parallel Algorithms for Chordal Graphs
• Fast and Simple Algorithms for Recognizing Chordal Comparability Graphs and Interval Graphs
• Helly circular-arc graph isomorphism is in logspace
• Incidence matrices and interval graphs
• Interval graphs: canonical representations in logspace
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Linear-time recognition of circular-arc graphs
• Maintaining knowledge about temporal intervals
• Network flows. Theory, algorithms, and applications.
• Nondeterministic Space is Closed under Complementation
• On the calculation of transitive reduction-closure of orders
• Realizing Interval Graphs with Size and Distance Constraints
• Reasoning about temporal relations, the tractable subalgebras of Allen's interval algebra
• Simultaneous interval graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The LBFS structure and recognition of interval graphs
• The method of forced enumeration for nondeterministic automata
• Undirected connectivity in log-space
• Uniform constant-depth threshold circuits for division and iterated multiplication.

Cited in

(15)

• On interval graphs and matrice profiles
• Parameterized complexity of perfectly matched sets
• Dimension of restricted classes of interval orders
• A graph-theoretic barcode ordering model for linked-reads
• Interval graph representation with given interval and intersection lengths
• Recognizing graphs with fixed interval number is NP-complete
• Interval graphs with side (and size) constraints
• Recognizing stick graphs with and without length constraints
• Stick graphs with length constraints
• FO model checking of interval graphs
• FO model checking of interval graphs
• Overlaying a hypergraph with a graph with bounded maximum degree
• Interval graphs: canonical representation in logspace
• On the isomorphism problem for Helly circular-arc graphs
• Graphs of interval count two with a given partition

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)