Minimum Cuts for Circular-Arc Graphs

DOI10.1137/0219071zbMATH Open0711.68060OpenAlexW1973146956MaRDI QIDQ3495653FDOQ3495653

Authors:

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

Recommendations

• Parallel algorithms on circular-arc graphs
• \(k\) best cuts for circular-arc graphs
• scientific article; zbMATH DE number 1555975
• Linear time algorithms on circular-arc graphs
• Dominating sets and domatic number of circular arc graphs

zbMATH Keywords

computational complexitycircular-arc graphsminimum cutmaximum independent setcircle graphminimum coveringalgebraic computation trees

Mathematics Subject Classification ID

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

Cited In (15)

• Minimum cut with the fewest number of arcs
• Power domination in circular-arc graphs
• Optimal separable partitioning in the plane
• A linear-time algorithm for finding locally connected spanning trees on circular-arc graphs
• Parallel algorithms on circular-arc graphs
• Powers of geometric intersection graphs and dispersion algorithms
• Title not available (Why is that?)
• On a circle-cover minimization problem
• Title not available (Why is that?)
• Two-Guard Walkability of Simple Polygons
• Efficient parallel recognition of some circular arc graphs. II
• \(k\) best cuts for circular-arc graphs
• Efficient parallel recognition of some circular arc graphs. I
• Finding an approximate minimum-link visibility path inside a simple polygon
• New results on induced matchings

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3495653)