Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
From MaRDI portal
Publication:4877525
DOI10.1137/S0097539792269095zbMath0858.05094OpenAlexW1969279846WikidataQ60307431 ScholiaQ60307431MaRDI QIDQ4877525
Jing Huang, Xiaotie Deng, Pavol Hell
Publication date: 4 June 1996
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539792269095
Analysis of algorithms and problem complexity (68Q25) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)
Related Items (87)
Subclasses of circular-arc bigraphs: Helly, normal and proper ⋮ On partitioning interval graphs into proper interval subgraphs and related problems ⋮ The Persistent Homology of Cyclic Graphs ⋮ From a Circular-Arc Model to a Proper Circular-Arc Model ⋮ Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection ⋮ Solving the canonical representation and star system problems for proper circular-arc graphs in logspace ⋮ Recognizing and representing proper interval graphs in parallel using merging and sorting ⋮ Shortest reconfiguration of sliding tokens on subclasses of interval graphs ⋮ Circular‐Arc Bigraphs and Its Subclasses ⋮ On the thinness and proper thinness of a graph ⋮ Polynomial kernels for proper interval completion and related problems ⋮ Satisfiability problems on intervals and unit intervals ⋮ Extending partial representations of circular-arc graphs ⋮ Asymptotics of the chromatic number for quasi-line graphs ⋮ Partial Characterizations of Circular-Arc Graphs ⋮ Efficient non-isomorphic graph enumeration algorithms for subclasses of perfect graphs ⋮ On the recognition of fuzzy circular interval graphs ⋮ Coloring fuzzy circular interval graphs ⋮ Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs ⋮ Random generation and enumeration of bipartite permutation graphs ⋮ Proper Helly Circular-Arc Graphs ⋮ Linear-time recognition of Helly circular-arc models and graphs ⋮ A dichotomy for minimum cost graph homomorphisms ⋮ Maximizing the strong triadic closure in split graphs and proper interval graphs ⋮ The \(k\)-in-a-path problem for claw-free graphs ⋮ A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs ⋮ Normal Helly circular-arc graphs and its subclasses ⋮ Proper interval vertex deletion ⋮ A fully dynamic algorithm for the recognition of \(P_4\)-sparse graphs ⋮ Recognition of probe proper interval graphs ⋮ Computing role assignments of proper interval graphs in polynomial time ⋮ A fully dynamic graph algorithm for recognizing interval graphs ⋮ Finding a smallest odd hole in a claw-free graph using global structure ⋮ A fully dynamic algorithm for modular decomposition and recognition of cographs. ⋮ Dynamic algorithms for monotonic interval scheduling problem ⋮ Induced subgraph isomorphism on proper interval and bipartite permutation graphs ⋮ A superlocal version of Reed's conjecture ⋮ Tractabilities and intractabilities on geometric intersection graphs ⋮ A certifying and dynamic algorithm for the recognition of proper circular-arc graphs ⋮ Interval graph representation with given interval and intersection lengths ⋮ The Roberts characterization of proper and unit interval graphs ⋮ A faster algorithm for the cluster editing problem on proper interval graphs ⋮ Template-driven rainbow coloring of proper interval graphs ⋮ Unit interval vertex deletion: fewer vertices are relevant ⋮ Unit interval editing is fixed-parameter tractable ⋮ Circular-arc hypergraphs: rigidity via connectedness ⋮ Recognizing Proper Tree-Graphs ⋮ Extending partial representations of proper and unit interval graphs ⋮ Powers of cycles, powers of paths, and distance graphs ⋮ Some remarks on the geodetic number of a graph ⋮ Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs ⋮ Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs ⋮ An optimal parallel algorithm for solving all-pairs shortest paths problem on circular-arc graphs ⋮ Template-driven rainbow coloring of proper interval graphs ⋮ Unnamed Item ⋮ Obstacle numbers of graphs ⋮ Intersection graphs of non-crossing paths ⋮ Induced Disjoint Paths in Claw-Free Graphs ⋮ NP-completeness results for edge modification problems ⋮ The clique operator on circular-arc graphs ⋮ A simple algorithm to find Hamiltonian cycles in proper interval graphs ⋮ Proper Interval Vertex Deletion ⋮ Bounding χ in terms of ω and Δ for quasi-line graphs ⋮ Random Generation and Enumeration of Proper Interval Graphs ⋮ A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs ⋮ A Lex-BFS-based recognition algorithm for Robinsonian matrices ⋮ Completing colored graphs to meet a target property ⋮ On the Carathéodory and exchange numbers of geodetic convexity in graphs ⋮ Shortest Reconfiguration of Sliding Tokens on a Caterpillar ⋮ Mutual exclusion scheduling with interval graphs or related classes. I ⋮ Total 2-domination of proper interval graphs ⋮ A linear time recognition algorithm for proper interval graphs ⋮ Claw‐Free Graphs, Skeletal Graphs, and a Stronger Conjecture on ω, Δ, and χ ⋮ Circularly Compatible Ones, $D$-Circularity, and Proper Circular-Arc Bigraphs ⋮ Unnamed Item ⋮ Partial characterizations of circular-arc graphs ⋮ A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs ⋮ A new representation of proper interval graphs with an application to clique-width ⋮ The hull number in the convexity of induced paths of order \(3\) ⋮ Characterizations and recognition of circular-arc graphs and subclasses: a survey ⋮ On the computation of the hull number of a graph ⋮ A dynamic distributed approach to representing proper interval graphs ⋮ Lexicographic Orientation Algorithms ⋮ Extending partial representations of subclasses of chordal graphs ⋮ Fully dynamic recognition of proper circular-arc graphs ⋮ On the isomorphism problem for Helly circular-arc graphs ⋮ Graphs and digraphs represented by intervals and circular arcs
This page was built for publication: Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
