Efficient algorithms for interval graphs and circular-arc graphs
From MaRDI portal
Cites work
Cited in
(87)- Mutual exclusion scheduling with interval graphs or related classes. I
- Optimal algorithm for a special point-labeling problem
- Some parallel algorithms on interval graphs
- On the domatic number of interval graphs
- Algorithmic aspects of intersection graphs and representation hypergraphs
- An 0(n log n\(+m\,\log \,\log \,n)\) maximum weight clique algorithm for circular-arc graphs
- Representations of graphs and networks (coding, layouts and embeddings)
- Linear time algorithms on circular-arc graphs
- New clique and independent set algorithms for circle graphs
- Processor optimization for flow graphs
- Maximum \(k\)-covering of weighted transitive graphs with applications
- Efficient parallel recognition of some circular arc graphs. I
- Optimal circular arc representations: Properties, recognition, and construction
- Clustering bipartite and chordal graphs: Complexity, sequential and parallel algorithms
- The maximum clique problem
- An exact algorithm for the maximum stable set problem
- An approximation algorithm for the license and shift class design problem
- The permutation-path coloring problem on trees.
- Finding a potential community in networks
- An optimal parallel algorithm for solving all-pairs shortest paths problem on circular-arc graphs
- Robust flows over time: models and complexity results
- Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach
- The allocation problem in hardware design
- On a 2-dimensional equipartition problem
- Achromatic number is NP-complete for cographs and interval graphs
- On the computational complexity of 2-interval pattern matching problems
- Optimal separable partitioning in the plane
- An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications
- Efficient approximation algorithms for domatic partition and on-line coloring of circular arc graphs
- On powers of circular arc graphs and proper circular arc graphs
- Packing chained items in aligned bins with applications to container transshipment and project scheduling
- Some variations on constrained minimum enclosing circle problem
- A linear-time algorithm for finding locally connected spanning trees on circular-arc graphs
- New results on induced matchings
- Air traffic flow management with layered workload constraints
- Generalised online colouring problems in overlap graphs
- Interval scheduling with economies of scale
- Computing \(k\)-centers of uncertain points on a real line
- Layered graphs: applications and algorithms
- Parameterized complexity of voter control in multi-peaked elections
- Online packet-routing in grids with bounded buffers
- Characterizing interval graphs which are probe unit interval graphs
- Computing and counting longest paths on circular-arc graphs in polynomial time
- The harmonious coloring problem is NP-complete for interval and permutation graphs
- Shiftable intervals
- A matrix characterization of interval and proper interval graphs
- Path problems in generalized stars, complete graphs, and brick wall graphs
- Inapproximability and approximability of maximal tree routing and coloring
- The stable set problem and the thinness of a graph
- Succinct encodings for families of interval graphs
- Vehicle scheduling under the warehouse-on-wheels policy
- Minimizing total completion time on a batching machine with job processing time compatibilities
- On partitioning interval graphs into proper interval subgraphs and related problems
- An exact decomposition approach for the real-time train dispatching problem
- Optimal parallel algorithm for shortest-paths problem on interval graphs
- Determining a set of maximum inscribed rectangles for label placement in a region
- A polynomial algorithm for the k-cluster problem on the interval graphs
- A triplet-based exact method for the shift minimisation personnel task scheduling problem
- A simple linear time algorithm for finding a maximum independent set of circular arcs using intervals alone
- One-dimensional \(k\)-center on uncertain data
- Determining DNA sequence similarity using maximum independent set algorithms for interval graphs
- Computing the all-pairs longest chains in the plane
- The complexity of colouring circle graphs (extended abstract)
- On the complexity of finding a potential community
- scientific article; zbMATH DE number 2230224 (Why is no real title available?)
- scientific article; zbMATH DE number 7651158 (Why is no real title available?)
- Parallel algorithms on circular-arc graphs
- Computing a maximum clique in geometric superclasses of disk graphs
- The complexity of path coloring and call scheduling
- Circular-arc graph coloring: On chords and circuits in the meeting graph
- Solving the edge‐disjoint paths problem using a two‐stage method
- Mobility offer allocations in corporate settings
- An optimal algorithm for the k-fixed-endpoint path cover on proper interval graphs
- Robust spectrum allocation in elastic flexgrid optical networks: complexity and formulations
- Restrictions of graph partition problems. I
- Approximation of MWIS on geometric intersection graphs
- Graph thinness: a lower bound and complexity
- A Lagrangian heuristic for satellite range scheduling with resource constraints
- (Multivariate) k-SUM as barrier to succinct computation
- Scheduling an unbounded batching machine with job processing time compatibilities
- On a circle-cover minimization problem
- Finding maximum cliques in arbitrary and in special graphs
- Approximating minimum coloring and maximum independent set in dotted interval graphs
- Maximum weight independent set of circular-arc graph and its application
- Selection of programme slots of television channels for giving advertisement: a graph theoretic approach
- Inapproximability and approximability of minimal tree routing and coloring
- Finding common structured patterns in linear graphs
This page was built for publication: Efficient algorithms for interval graphs and circular-arc graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3956413)
