Unit Circular-Arc Graph Representations and Feasible Circulations

DOI10.1137/060650805zbMath1232.05145OpenAlexW2074290344MaRDI 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

zbMATH Keywords

algorithmnetworkscircular-arc graphcirculationscircular-arc modelproper circular-arc graphunit circular-arc graph

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (13)

Solving the canonical representation and star system problems for proper circular-arc graphs in logspace ⋮ Essential obstacles to Helly circular-arc graphs ⋮ Linear-time recognition of Helly circular-arc models and graphs ⋮ A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs ⋮ On the structure of (pan, even hole)‐free graphs ⋮ Normal Helly circular-arc graphs and its subclasses ⋮ 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 ⋮ 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 ⋮ Short Models for Unit Interval Graphs ⋮ Characterizations and recognition of circular-arc graphs and subclasses: a survey

This page was built for publication: Unit Circular-Arc Graph Representations and Feasible Circulations