Minimum Cuts for Circular-Arc Graphs

DOI10.1137/0219071zbMath0711.68060OpenAlexW1973146956MaRDI QIDQ3495653

No author found.

Publication date: 1990

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0219071

zbMATH Keywords

computational complexityminimum cutmaximum independent setcircular-arc graphscircle graphminimum coveringalgebraic computation trees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Management decision making, including multiple objectives (90B50) Parallel algorithms in computer science (68W10)

Related Items (11)

Optimal separable partitioning in the plane ⋮ \(k\) best cuts for circular-arc graphs ⋮ Power domination in circular-arc graphs ⋮ A linear-time algorithm for finding locally connected spanning trees on circular-arc graphs ⋮ Powers of geometric intersection graphs and dispersion algorithms ⋮ New results on induced matchings ⋮ Finding an approximate minimum-link visibility path inside a simple polygon ⋮ Efficient parallel recognition of some circular arc graphs. II ⋮ Efficient parallel recognition of some circular arc graphs. I ⋮ Parallel algorithms on circular-arc graphs ⋮ Two-Guard Walkability of Simple Polygons

This page was built for publication: Minimum Cuts for Circular-Arc Graphs