On the public citation graph

An Incremental Linear-Time Algorithm for Recognizing Interval Graphs

0 signed · 154 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1007/978-94-009-5315-4_2openalex-snapshot
Algorithmic Aspects of Comparability Graphs and Interval Graphs
inferredcites →https://doi.org/10.1016/0012-365x(85)90039-1openalex-snapshot
Interval graphs and related topics
inferredcites →https://doi.org/10.1016/0771-050x(80)90036-4openalex-snapshot
Algorithmic graph theory and perfect graphs
inferredcites →https://doi.org/10.1016/s0022-0000(76)80045-1openalex-snapshot
Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
inferredcites →https://doi.org/10.1109/tcad.1987.1270248openalex-snapshot
Exact and Approximate Solutions for the Gate Matrix Layout Problem
inferredcites →https://doi.org/10.1137/0205021openalex-snapshot
Algorithmic Aspects of Vertex Elimination on Graphs
inferredcites →https://doi.org/10.1137/0213035openalex-snapshot
Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
inferredcites →https://doi.org/10.1137/0606031openalex-snapshot
Amortized Computational Complexity
inferredcites →https://doi.org/10.2140/pjm.1965.15.835openalex-snapshot
Incidence matrices and interval graphs

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1002/jgt.22792openalex-snapshot
Recognizing interval bigraphs by forbidden patterns
inferred← citeshttps://doi.org/10.1006/jagm.2001.1205openalex-snapshot
A Simple Test for the Consecutive Ones Property
inferred← citeshttps://doi.org/10.1007/3-540-44634-6_28openalex-snapshot
Higher-Dimensional Packing with Order Constraints
inferred← citeshttps://doi.org/10.1007/3-540-44679-6_23openalex-snapshot
PC-Trees vs. PQ-Trees
inferred← citeshttps://doi.org/10.1007/3-540-44867-5_16openalex-snapshot
A Clustering Algorithm for Interval Graph Test on Noisy Data
inferred← citeshttps://doi.org/10.1007/3-540-44968-x_38openalex-snapshot
The Complexity of Physical Mapping with Strict Chimerism
inferred← citeshttps://doi.org/10.1007/3-540-53832-1_45openalex-snapshot
Remarks on some concurrency measures
inferred← citeshttps://doi.org/10.1007/3-540-54891-2_22openalex-snapshot
A new simple linear algorithm to recognize interval graphs
inferred← citeshttps://doi.org/10.1007/3-540-54945-5_49openalex-snapshot
Substitution decomposition on chordal graphs and applications
inferred← citeshttps://doi.org/10.1007/3-540-56279-6_98openalex-snapshot
A simple test for the consecutive ones property
inferred← citeshttps://doi.org/10.1007/3-540-56402-0_31openalex-snapshot
A simple test for interval graphs
inferred← citeshttps://doi.org/10.1007/3-540-58950-3_375openalex-snapshot
Characterization and recognition of point-halfspace and related orders
inferred← citeshttps://doi.org/10.1007/3-540-60313-1_140openalex-snapshot
Interval graphs with side (and size) constraints
inferred← citeshttps://doi.org/10.1007/3-540-61576-8_70openalex-snapshot
On-line recognition of interval graphs in O(m+nlog n) time
inferred← citeshttps://doi.org/10.1007/3-540-63397-9_12openalex-snapshot
A new exact algorithm for general orthogonal d-dimensional knapsack problems
inferred← citeshttps://doi.org/10.1007/978-1-4419-7997-1_26openalex-snapshot
Algorithmic Aspects of Domination in Graphs
inferred← citeshttps://doi.org/10.1007/978-1-4613-0303-9_28openalex-snapshot
Algorithmic Aspects of Domination in Graphs
inferred← citeshttps://doi.org/10.1007/978-1-4939-2864-4_686openalex-snapshot
Split decomposition, circle graphs and related graph families
inferred← citeshttps://doi.org/10.1007/978-3-030-60440-0_9openalex-snapshot
Graph Isomorphism Restricted by Lists
inferred← citeshttps://doi.org/10.1007/978-3-031-22203-0_30openalex-snapshot
Coloring Mixed and Directional Interval Graphs
inferred← citeshttps://doi.org/10.1007/978-3-032-11835-6_29openalex-snapshot
Interval k-graphs : Recognition and Forbidden Obstructions
inferred← citeshttps://doi.org/10.1007/978-3-319-12340-0_19openalex-snapshot
Induced Disjoint Paths in Circular-Arc Graphs in Linear Time
inferred← citeshttps://doi.org/10.1007/978-3-319-13075-0_32openalex-snapshot
Minimal Obstructions for Partial Representations of Interval Graphs
inferred← citeshttps://doi.org/10.1007/978-3-319-30139-6_19openalex-snapshot
Shortest Reconfiguration of Sliding Tokens on a Caterpillar
inferred← citeshttps://doi.org/10.1007/978-3-319-44543-4_13openalex-snapshot
Reconfiguration of Steiner Trees in an Unweighted Graph
inferred← citeshttps://doi.org/10.1007/978-3-319-68705-6_22openalex-snapshot
Enumeration and Maximum Number of Maximal Irredundant Sets for Chordal Graphs
inferred← citeshttps://doi.org/10.1007/978-3-319-75172-6_2openalex-snapshot
Enumeration of Nonisomorphic Interval Graphs and Nonisomorphic Permutation Graphs
inferred← citeshttps://doi.org/10.1007/978-3-540-28634-9_13openalex-snapshot
Range-Free Ranking in Sensors Networks and Its Applications to Localization
inferred← citeshttps://doi.org/10.1007/978-3-540-30551-4_73openalex-snapshot
Canonical Data Structure for Interval Probe Graphs
inferred← citeshttps://doi.org/10.1007/978-3-540-30551-4_74openalex-snapshot
Efficient Algorithms for the Longest Path Problem
inferred← citeshttps://doi.org/10.1007/978-3-540-30559-0_1openalex-snapshot
Lexicographic Breadth First Search – A Survey
inferred← citeshttps://doi.org/10.1007/978-3-540-39890-5_11openalex-snapshot
A Simple Linear Time LexBFS Cograph Recognition Algorithm
inferred← citeshttps://doi.org/10.1007/978-3-540-69903-3_32openalex-snapshot
A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs
inferred← citeshttps://doi.org/10.1007/978-3-642-00202-1_17openalex-snapshot
A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs
inferred← citeshttps://doi.org/10.1007/978-3-642-02882-3_12openalex-snapshot
Reconstruction of Interval Graphs
inferred← citeshttps://doi.org/10.1007/978-3-642-11409-0_7openalex-snapshot
Fully Dynamic Representations of Interval Graphs
inferred← citeshttps://doi.org/10.1007/978-3-642-13562-0_17openalex-snapshot
An ${\mathcal{O}}(n^2)$ -time Algorithm for the Minimal Interval Completion Problem
inferred← citeshttps://doi.org/10.1007/978-3-642-13962-8_8openalex-snapshot
A Faster Algorithm for Finding Minimum Tucker Submatrices
inferred← citeshttps://doi.org/10.1007/978-3-642-20712-9_29openalex-snapshot
A Polynomial-Time Algorithm for Finding a Minimal Conflicting Set Containing a Given Row
inferred← citeshttps://doi.org/10.1007/978-3-642-20877-5_28openalex-snapshot
Extending Partial Representations of Interval Graphs
inferred← citeshttps://doi.org/10.1007/978-3-642-20877-5_35openalex-snapshot
Catching a Fast Robber on Interval Graphs
inferred← citeshttps://doi.org/10.1007/978-3-642-27848-8_686-1openalex-snapshot
Split Decomposition via Graph-Labelled Trees
inferred← citeshttps://doi.org/10.1007/978-3-642-32278-5_9openalex-snapshot
Colorings
inferred← citeshttps://doi.org/10.1007/978-3-642-45281-9_7openalex-snapshot
On Complexity of Flooding Games on Graphs with Interval Representations
inferred← citeshttps://doi.org/10.1007/978-3-642-60744-8_24openalex-snapshot
An exact algorithm for general orthogonal n-dimensional knapsack problems
inferred← citeshttps://doi.org/10.1007/bfb0028546openalex-snapshot
A synthesis on partition refinement: A useful routine for strings, graphs, boolean matrices and automata
inferred← citeshttps://doi.org/10.1007/bfb0035164openalex-snapshot
Interval graphs, interval orders and the consistency of temporal events (extended abstract)
inferred← citeshttps://doi.org/10.1007/s00224-012-9388-1openalex-snapshot
A Faster Algorithm for Finding Minimum Tucker Submatrices
inferred← citeshttps://doi.org/10.1007/s00453-009-9291-6openalex-snapshot
A Fully Dynamic Graph Algorithm for Recognizing Interval Graphs
inferred← citeshttps://doi.org/10.1007/s00453-018-0481-yopenalex-snapshot
On the Classes of Interval Graphs of Limited Nesting and Count of Lengths
inferred← citeshttps://doi.org/10.1007/s10852-011-9159-zopenalex-snapshot
MPQ-trees for the Orthogonal Packing Problem
inferred← citeshttps://doi.org/10.1016/0012-365x(93)90353-uopenalex-snapshot
Counting endpoint sequences for interval orders and interval graphs
inferred← citeshttps://doi.org/10.1016/0020-0190(95)00024-7openalex-snapshot
A note on lexicographic breadth first search for chordal graphs
inferred← citeshttps://doi.org/10.1016/0020-0190(95)00046-fopenalex-snapshot
Simple linear time recognition of unit interval graphs
inferred← citeshttps://doi.org/10.1016/0020-0190(95)00133-wopenalex-snapshot
A linear-time algorithm for proper interval graph recognition
inferred← citeshttps://doi.org/10.1016/0166-218x(92)00036-lopenalex-snapshot
Periodic assignment and graph colouring
inferred← citeshttps://doi.org/10.1016/0166-218x(94)00067-3openalex-snapshot
Weighted independent perfect domination on cocomparability graphs
inferred← citeshttps://doi.org/10.1016/b978-0-444-87358-3.50006-7openalex-snapshot
THE ORDER-THEORETIC APPROACH TO SCHEDULING: THE DETERMINISTIC CASE
inferred← citeshttps://doi.org/10.1016/j.dam.2003.07.001openalex-snapshot
A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
inferred← citeshttps://doi.org/10.1016/j.dam.2004.10.001openalex-snapshot
Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
inferred← citeshttps://doi.org/10.1016/j.dam.2005.09.010openalex-snapshot
On the interval completion of chordal graphs
inferred← citeshttps://doi.org/10.1016/j.dam.2008.06.028openalex-snapshot
Dynamically maintaining split graphs
inferred← citeshttps://doi.org/10.1016/j.dam.2012.11.005openalex-snapshot
Normal Helly circular-arc graphs and its subclasses
inferred← citeshttps://doi.org/10.1016/j.dam.2016.02.009openalex-snapshot
Strict chordal and strict split digraphs
inferred← citeshttps://doi.org/10.1016/j.dam.2018.05.041openalex-snapshot
Chronological rectangle digraphs which are two-terminal series–parallel
inferred← citeshttps://doi.org/10.1016/j.dam.2019.03.018openalex-snapshot
Enumeration and maximum number of maximal irredundant sets for chordal graphs
inferred← citeshttps://doi.org/10.1016/j.dam.2024.08.016openalex-snapshot
Semi-proper interval graphs
inferred← citeshttps://doi.org/10.1016/j.endm.2010.05.054openalex-snapshot
MPQ-trees for orthogonal packing problem
inferred← citeshttps://doi.org/10.1016/j.ipl.2009.07.010openalex-snapshot
A simple algorithm to find Hamiltonian cycles in proper interval graphs
inferred← citeshttps://doi.org/10.1016/j.ipl.2017.04.007openalex-snapshot
Computing the clique-separator graph for an interval graph in linear time
inferred← citeshttps://doi.org/10.1016/j.jcss.2009.07.001openalex-snapshot
Approximation and fixed-parameter algorithms for consecutive ones submatrix problems
inferred← citeshttps://doi.org/10.1016/j.tcs.2009.08.012openalex-snapshot
Scale free interval graphs
inferred← citeshttps://doi.org/10.1016/j.tcs.2010.07.006openalex-snapshot
Reconstruction of interval graphs
inferred← citeshttps://doi.org/10.1016/j.tcs.2012.12.031openalex-snapshot
An O(n2) -time algorithm for the minimal interval completion problem
inferred← citeshttps://doi.org/10.1016/j.tcs.2016.06.003openalex-snapshot
Induced disjoint paths in circular-arc graphs in linear time
inferred← citeshttps://doi.org/10.1016/j.tcs.2016.08.016openalex-snapshot
The complexity of dominating set reconfiguration
inferred← citeshttps://doi.org/10.1016/j.tcs.2018.09.031openalex-snapshot
Cops, a fast robber and defensive domination on interval graphs
inferred← citeshttps://doi.org/10.1016/j.tcs.2019.01.007openalex-snapshot
Fully dynamic representations of interval graphs
inferred← citeshttps://doi.org/10.1016/j.tcs.2019.04.017openalex-snapshot
Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs
inferred← citeshttps://doi.org/10.1016/j.tcs.2021.02.019openalex-snapshot
Shortest reconfiguration of sliding tokens on subclasses of interval graphs
inferred← citeshttps://doi.org/10.1016/s0004-3702(03)00015-8openalex-snapshot
BOB: Improved winner determination in combinatorial auctions and generalizations
inferred← citeshttps://doi.org/10.1016/s0020-0190(03)00298-9openalex-snapshot
A linear time recognition algorithm for proper interval graphs
inferred← citeshttps://doi.org/10.1016/s0020-0190(96)00193-7openalex-snapshot
A linear-time algorithm for the weighted feedback vertex problem on interval graphs
inferred← citeshttps://doi.org/10.1016/s0020-0190(98)00040-4openalex-snapshot
Weighted irredundance of interval graphs
inferred← citeshttps://doi.org/10.1016/s0166-218x(97)00014-0openalex-snapshot
On minimum intersection of two minimum dominating sets of interval graphs
inferred← citeshttps://doi.org/10.1016/s0166-218x(98)00077-8openalex-snapshot
On probe interval graphs
inferred← citeshttps://doi.org/10.1016/s0304-3975(02)00435-8openalex-snapshot
PC trees and circular-ones arrangements
inferred← citeshttps://doi.org/10.1016/s0304-3975(96)00208-3openalex-snapshot
Satisfiability problems on intervals and unit intervals
inferred← citeshttps://doi.org/10.1016/s0304-3975(97)00241-7openalex-snapshot
Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
inferred← citeshttps://doi.org/10.1016/s0378-1119(03)00825-4openalex-snapshot
Barnacle: an assembly algorithm for clone-based sequences of whole genomes
inferred← citeshttps://doi.org/10.1016/s0927-0507(05)80112-4openalex-snapshot
Chapter 8 VLSI network design
inferred← citeshttps://doi.org/10.1023/a:1006209905006openalex-snapshot
Finiteness Theorems for Graphs and Posets Obtained by Compositions
inferred← citeshttps://doi.org/10.1023/a:1009717525330openalex-snapshot
Temporal Constraints: A Survey
inferred← citeshttps://doi.org/10.1023/a:1009850020378openalex-snapshot
Tagged Probe Interval Graphs
inferred← citeshttps://doi.org/10.1089/cmb.1995.2.139openalex-snapshot
Four Strikes Against Physical Mapping of DNA
inferred← citeshttps://doi.org/10.1109/aiccsa.2009.5069309openalex-snapshot
Filtering algorithms for sequencing constraints: Application in physical mapping
inferred← citeshttps://doi.org/10.1109/hicss.1997.667212openalex-snapshot
Improved efficient parallel algorithms to recognize interval graphs and interval hypergraphs
inferred← citeshttps://doi.org/10.1109/hicss.1998.649268openalex-snapshot
On the problem of tracking mobile users in wireless communications networks
inferred← citeshttps://doi.org/10.1109/jcit.1990.128360openalex-snapshot
A combinatorial approach to temporal reasoning
inferred← citeshttps://doi.org/10.1137/060664690openalex-snapshot
A Simple Linear Time LexBFS Cograph Recognition Algorithm
inferred← citeshttps://doi.org/10.1137/060665713openalex-snapshot
Higher‐Dimensional Packing with Order Constraints
inferred← citeshttps://doi.org/10.1137/1.9781611974331.ch77openalex-snapshot
Linear Recognition of Almost Interval Graphs
inferred← citeshttps://doi.org/10.1137/1.9781611976496.11openalex-snapshot
Recognizing (Unit) Interval Graphs by Zigzag Graph Searches
inferred← citeshttps://doi.org/10.1137/s0097539703437855openalex-snapshot
Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
inferred← citeshttps://doi.org/10.1137/s0097539792224814openalex-snapshot
Fast and Simple Algorithms for Recognizing Chordal Comparability Graphs and Interval Graphs
inferred← citeshttps://doi.org/10.1137/s0097539792238431openalex-snapshot
Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
inferred← citeshttps://doi.org/10.1137/s0097539792269095openalex-snapshot
Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
inferred← citeshttps://doi.org/10.1137/s0097539793258143openalex-snapshot
Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
inferred← citeshttps://doi.org/10.1137/s0895480100373455openalex-snapshot
The LBFS Structure and Recognition of Interval Graphs
inferred← citeshttps://doi.org/10.1137/s0895480196306373openalex-snapshot
Realizing Interval Graphs with Size and Distance Constraints
inferred← citeshttps://doi.org/10.1137/s0895480197322154openalex-snapshot
Convex-Round and Concave-Round Graphs
inferred← citeshttps://doi.org/10.1142/s0129054107005054openalex-snapshot
ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES
inferred← citeshttps://doi.org/10.1142/s0129054199000125openalex-snapshot
PARTITION REFINEMENT TECHNIQUES: AN INTERESTING ALGORITHMIC TOOL KIT
inferred← citeshttps://doi.org/10.1145/1250910.1250934openalex-snapshot
On the complexity of combinatorial auctions
inferred← citeshttps://doi.org/10.1145/167088.167170openalex-snapshot
Mapping the genome
inferred← citeshttps://doi.org/10.1145/174147.169675openalex-snapshot
Complexity and algorithms for reasoning about time
inferred← citeshttps://doi.org/10.1201/9781420035179.ch32openalex-snapshot
PQ Trees, PC Trees, and Planar Graphs
inferred← citeshttps://doi.org/10.1287/moor.1030.0079openalex-snapshot
A Combinatorial Characterization of Higher-Dimensional Orthogonal Packing
inferred← citeshttps://doi.org/10.1287/opre.1060.0369openalex-snapshot
An Exact Algorithm for Higher-Dimensional Orthogonal Packing
inferred← citeshttps://doi.org/10.14288/1.0052159openalex-snapshot
Variants of the Consecutive-Ones Property motivated by the reconstruction of ancestral species
inferred← citeshttps://doi.org/10.1587/transfun.e100.a.1532openalex-snapshot
Reconfiguration of Steiner Trees in an Unweighted Graph
inferred← citeshttps://doi.org/10.1587/transinf.2018edp7047openalex-snapshot
A Linear-Time Algorithm for Finding a Spanning Tree with Non-Terminal Set VNT on Interval Graphs
inferred← citeshttps://doi.org/10.1587/transinf.2021edp7175openalex-snapshot
A Polynomial-Time Algorithm for Finding a Spanning Tree with Non-Terminal Set VNT on Circular-Arc Graphs
inferred← citeshttps://doi.org/10.23638/dmtcs-21-1-13openalex-snapshot
On the End-Vertex Problem of Graph Searches
inferred← citeshttps://doi.org/10.32657/10356/51122openalex-snapshot
Representations of tolerance graphs
inferred← citeshttps://doi.org/10.4230/lipics.stacs.2015.540openalex-snapshot
Automorphism Groups of Geometrically Represented Graphs
inferred← citeshttps://doi.org/10.46298/dmtcs.13355openalex-snapshot
Simpler and Unified Recognition Algorithm for Path Graphs and Directed Path Graphs
inferred← citeshttps://doi.org/10.46298/dmtcs.2081openalex-snapshot
Influence of the tie-break rule on the end-vertex problem
inferred← citeshttps://doi.org/10.46298/dmtcs.2094openalex-snapshot
A four-sweep LBFS recognition algorithm for interval graphs
inferred← citeshttps://doi.org/10.46298/dmtcs.269openalex-snapshot
Linear time recognition of P4-indifference graphs
inferred← citeshttps://doi.org/10.46298/dmtcs.6164openalex-snapshot
Efficient enumeration of non-isomorphic interval graphs
inferred← citeshttps://doi.org/10.46298/dmtcs.625openalex-snapshot
Isomorphism of graph classes related to the circular-ones property
inferred← citeshttps://doi.org/10.48550/arxiv.1203.4822openalex-snapshot
Isomorphism of graph classes related to the circular-ones property
inferred← citeshttps://doi.org/10.48550/arxiv.1503.00833openalex-snapshot
The complexity of dominating set reconfiguration
inferred← citeshttps://doi.org/10.48550/arxiv.cs/0308006openalex-snapshot
Higher-Dimensional Packing with Order Constraints
inferred← citeshttps://doi.org/10.5120/10445-5136openalex-snapshot
Detection of Linkage Patterns Repeating across Multiple Sequential Data
inferred← citeshttps://doi.org/10.5540/tema.2007.08.01.0001openalex-snapshot
On the Representation of a PI-Graph
inferred← citeshttps://doi.org/10.5555/314613.314697openalex-snapshot
The ultimate interval graph recognition algorithm
inferred← citeshttps://doi.org/10.5555/644108.644137openalex-snapshot
Certifying algorithms for recognizing interval graphs and permutation graphs
inferred← citeshttps://doi.org/10.5555/982792.982909openalex-snapshot
A certifying algorithm for the consecutive-ones property
inferred← citeshttps://doi.org/10.5772/33302openalex-snapshot
Recent Advances in Multi-dimensional Packing Problems
inferred← citeshttps://doi.org/10.70675/16ba22e2z4afbz4587zad85zfd3b9a66a7faopenalex-snapshot
Problèmes de placement 2D et application à l’ordonnancement : modélisation par la théorie des graphes et approches de programmation mathématique
inferred← citeshttps://doi.org/10.70675/e6355c4bz172az40e5z90a6ze5635bc0e918openalex-snapshot
Structural and algorithmic aspects of (multiple) interval graphs
inferred← citeshttps://doi.org/10.7155/jgaa.00293openalex-snapshot
Maximal Neighborhood Search and Rigid Interval Graphs
inferred← citeshttps://doi.org/10.7282/t3cz37jcopenalex-snapshot
Computational approaches to identifying molecular associations in high-throughput biological data
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.