Solving the canonical representation and star system problems for proper circular-arc graphs in logspace

DOI10.1016/j.jda.2016.03.001zbMath1355.68124arXiv1202.4406OpenAlexW1484984100MaRDI QIDQ350727

Sebastian Kuhnert, Oleg Verbitsky, Johannes Köbler

Publication date: 9 December 2016

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1202.4406

zbMATH Keywords

intersection graphsgraph isomorphismlogspacecircular-ones property

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (6)

Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter I: theory ⋮ Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter II: algorithms ⋮ Characterization of 2-path signed network ⋮ Circular-arc hypergraphs: rigidity via connectedness ⋮ Canonical representations for circular-arc graphs using flip sets ⋮ Circularly Compatible Ones, $D$-Circularity, and Proper Circular-Arc Bigraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient parallel recognition of some circular arc graphs. II
• Intersection representations of matrices by subtrees and unicycles on graphs
• Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs
• Le problème d'étoiles pour graphes est NP-complèt
• Efficient parallel recognition of some circular arc graphs. I
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• On testing consecutive-ones property in parallel
• Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits
• Efficient graph representations
• PC trees and circular-ones arrangements.
• Linear-time recognition of circular-arc graphs
• Fully dynamic recognition of proper circular-arc graphs
• On the compatibility between a graph and a simple order
• Matrix characterizations of circular-arc graphs
• Structure theorems for some circular-arc graphs
• Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Logspace
• Interval Graphs: Canonical Representations in Logspace
• A Simple Test for the Consecutive Ones Property
• On the complexity of reconstructing H-free graphs from their Star Systems
• Parallel recognition of the consecutive ones property with applications
• A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs
• Undirected connectivity in log-space
• Unit Circular-Arc Graph Representations and Feasible Circulations
• A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• Reconstructing a Graph from its Neighborhood Lists
• Convex-Round and Concave-Round Graphs
• $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
• Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Neighborhood hypergraphs of bipartite graphs

This page was built for publication: Solving the canonical representation and star system problems for proper circular-arc graphs in logspace