Efficient algorithms for interval graphs and circular-arc graphs
From MaRDI portal
Publication:3956413
DOI10.1002/net.3230120410zbMath0493.68066OpenAlexW2049520215MaRDI QIDQ3956413
No author found.
Publication date: 1982
Published in: Networks (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/net.3230120410
maximum independent setmaximum cliqueminimum covering by disjoint completely connected sets of cliques
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10)
Related Items (83)
Vehicle scheduling under the warehouse-on-wheels policy ⋮ An exact algorithm for the maximum stable set problem ⋮ An approximation algorithm for the license and shift class design problem ⋮ On the Complexity of Finding a Potential Community ⋮ On the computational complexity of 2-interval pattern matching problems ⋮ A simple linear time algorithm for finding a maximum independent set of circular arcs using intervals alone ⋮ On partitioning interval graphs into proper interval subgraphs and related problems ⋮ A Triplet-Based Exact Method for the Shift Minimisation Personnel Task Scheduling Problem ⋮ Optimal separable partitioning in the plane ⋮ Approximating minimum coloring and maximum independent set in dotted interval graphs ⋮ Determining DNA sequence similarity using maximum independent set algorithms for interval graphs ⋮ Some parallel algorithms on interval graphs ⋮ Computing the all-pairs longest chains in the plane ⋮ An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications ⋮ The stable set problem and the thinness of a graph ⋮ Computing \(k\)-centers of uncertain points on a real line ⋮ Maximum weight independent set of circular-arc graph and its application ⋮ On the domatic number of interval graphs ⋮ An Exact Decomposition Approach for the Real-Time Train Dispatching Problem ⋮ Algorithmic aspects of intersection graphs and representation hypergraphs ⋮ Efficient approximation algorithms for domatic partition and on-line coloring of circular arc graphs ⋮ Succinct encodings for families of interval graphs ⋮ An 0(n log n\(+m\,\log \,\log \,n)\) maximum weight clique algorithm for circular-arc graphs ⋮ Online packet-routing in grids with bounded buffers ⋮ On powers of circular arc graphs and proper circular arc graphs ⋮ Selection of programme slots of television channels for giving advertisement: a graph theoretic approach ⋮ The complexity of colouring circle graphs ⋮ Characterizing interval graphs which are probe unit interval graphs ⋮ Solving the edge‐disjoint paths problem using a two‐stage method ⋮ Packing chained items in aligned bins with applications to container transshipment and project scheduling ⋮ Mobility offer allocations in corporate settings ⋮ The permutation-path coloring problem on trees. ⋮ An optimal algorithm for the \(k\)-fixed-endpoint path cover on proper interval graphs ⋮ Unnamed Item ⋮ Some variations on constrained minimum enclosing circle problem ⋮ A linear-time algorithm for finding locally connected spanning trees on circular-arc graphs ⋮ Computing and counting longest paths on circular-arc graphs in polynomial time ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ The harmonious coloring problem is NP-complete for interval and permutation graphs ⋮ Inapproximability and approximability of minimal tree routing and coloring ⋮ New results on induced matchings ⋮ Linear time algorithms on circular-arc graphs ⋮ Finding a potential community in networks ⋮ New clique and independent set algorithms for circle graphs ⋮ One-dimensional \(k\)-center on uncertain data ⋮ Restrictions of graph partition problems. I ⋮ Parallel algorithms on circular-arc graphs ⋮ Processor optimization for flow graphs ⋮ Shiftable intervals ⋮ Maximum \(k\)-covering of weighted transitive graphs with applications ⋮ A matrix characterization of interval and proper interval graphs ⋮ Efficient parallel recognition of some circular arc graphs. I ⋮ An optimal parallel algorithm for solving all-pairs shortest paths problem on circular-arc graphs ⋮ Path problems in generalized stars, complete graphs, and brick wall graphs ⋮ Finding common structured patterns in linear graphs ⋮ The complexity of path coloring and call scheduling ⋮ Unnamed Item ⋮ Inapproximability and approximability of maximal tree routing and coloring ⋮ A Lagrangian heuristic for satellite range scheduling with resource constraints ⋮ Circular-arc graph coloring: On chords and circuits in the meeting graph ⋮ Air traffic flow management with layered workload constraints ⋮ Robust flows over time: models and complexity results ⋮ Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach ⋮ Generalised online colouring problems in overlap graphs ⋮ Layered graphs: applications and algorithms ⋮ Optimal parallel algorithm for shortest-paths problem on interval graphs ⋮ Mutual exclusion scheduling with interval graphs or related classes. I ⋮ Computing a maximum clique in geometric superclasses of disk graphs ⋮ The allocation problem in hardware design ⋮ On a 2-dimensional equipartition problem ⋮ Optimal circular arc representations: Properties, recognition, and construction ⋮ Optimal algorithm for a special point-labeling problem ⋮ Scheduling an unbounded batching machine with job processing time compatibilities ⋮ DETERMINING A SET OF MAXIMUM INSCRIBED RECTANGLES FOR LABEL PLACEMENT IN A REGION ⋮ Unnamed Item ⋮ Achromatic number is NP-complete for cographs and interval graphs ⋮ Clustering bipartite and chordal graphs: Complexity, sequential and parallel algorithms ⋮ Parameterized complexity of voter control in multi-peaked elections ⋮ On a circle-cover minimization problem ⋮ A polynomial algorithm for the k-cluster problem on the interval graphs ⋮ Interval scheduling with economies of scale ⋮ Finding maximum cliques in arbitrary and in special graphs ⋮ The maximum clique problem
Cites Work
This page was built for publication: Efficient algorithms for interval graphs and circular-arc graphs
