Minimum Cuts for Circular-Arc Graphs

DOI10.1137/0219071MaRDI QIDQ3495653zbMATH OpenOpenAlexFDO

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

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)

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

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
• scientific article; zbMATH DE number 7236457 (Why is no real title available?)
• On a circle-cover minimization problem
• scientific article; zbMATH DE number 1555975 (Why is no real title available?)
• Efficient parallel recognition of some circular arc graphs. II
• Two-Guard Walkability of Simple Polygons
• \(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)