Unit Circular-Arc Graph Representations and Feasible Circulations
From MaRDI portal
Publication:3614215
DOI10.1137/060650805zbMath1232.05145MaRDI QIDQ3614215
Min Chih Lin, Jayme Luiz Szwarcfiter
Publication date: 16 March 2009
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/9cd2e1b3f2aa91570d8dddba4f52f2d4008fd8e8
algorithm; networks; circular-arc graph; circulations; circular-arc model; proper circular-arc graph; unit circular-arc graph
05C05: Trees
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
05C62: Graph representations (geometric and intersection representations, etc.)
Related Items
On the structure of (pan, even hole)‐free graphs, Solving the canonical representation and star system problems for proper circular-arc graphs in logspace, Linear-time recognition of Helly circular-arc models and graphs, Boxicity of circular arc graphs, Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs, The clique operator on circular-arc graphs, Characterizations and recognition of circular-arc graphs and subclasses: a survey, Normal Helly circular-arc graphs and its subclasses, Essential obstacles to Helly circular-arc graphs, Short Models for Unit Interval Graphs, 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, A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs
