Search results for "interval graphs"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
4	Toshiki Saitoh, Katsuhisa Yamanaka, Masashi Kiyomi, Ryuhei Uehara	Random Generation and Enumeration of Proper Interval Graphs.	WALCOM	2009	DBLP DOI BibTeX RDF	proper interval graphs, unit interval graphs, enumeration, Counting, random generation
4	Philippe Gambette, Stéphane Vialette	On Restrictions of Balanced 2-Interval Graphs.	WG	2007	DBLP DOI BibTeX RDF	2-interval graphs, graph classes, quasi-line graphs, circular interval graphs, scheduling, bioinformatics, line graphs, claw-free graphs
3	Kyriaki Ioannidou, George B. Mertzios, Stavros D. Nikolopoulos	The Longest Path Problem Is Polynomial on Interval Graphs.	MFCS	2009	DBLP DOI BibTeX RDF	Longest path problem, complexity, dynamic programming, interval graphs, polynomial algorithm
3	Masashi Kiyomi, Toshiki Saitoh, Ryuhei Uehara	Reconstruction of Interval Graphs.	COCOON	2009	DBLP DOI BibTeX RDF	the graph reconstruction conjecture, polynomial time algorithm, interval graphs
3	Naoto Miyoshi, Takeya Shigezumi, Ryuhei Uehara, Osamu Watanabe	Scale Free Interval Graphs.	AAIM	2008	DBLP DOI BibTeX RDF	scale free graph, interval graphs, small world network
3	Andreas Brandstädt, Christian Hundt	Ptolemaic Graphs and Interval Graphs Are Leaf Powers.	LATIN	2008	DBLP DOI BibTeX RDF	and Classification Leaf powers, leaf roots, strongly chordal graphs, ptolemaic graphs, graph class inclusions, (unit) interval graphs, clique-width, graph powers
3	Yerim Chung, Jean-François Culus, Marc Demange	Inverse Booking Problem: Inverse Chromatic Number Problem in Interval Graphs.	WALCOM	2008	DBLP DOI BibTeX RDF	Inverse combinatorial optimization, Inverse chromatic number problem, Machine(s)-scheduling with earliness and or tardiness costs, Approximation, NP-hardness, Interval graphs
3	Tiziana Calamoneri, Saverio Caminiti, Stephan Olariu, Rossella Petreschi	On the L(h, k)-Labeling of Co-comparability Graphs.	ESCAPE	2007	DBLP DOI BibTeX RDF	L(h and k)-Labeling, co-comparability graphs, unit-interval graphs, interval graphs
3	Frédéric Gardi	Mutual exclusion scheduling with interval graphs or related classes: Complexity and algorithms.	4OR	2006	DBLP DOI BibTeX RDF	Mutual exclusion scheduling, workforce planning, graph classes, graph coloring, interval graphs
3	Martin Farach-Colton, Yang Huang, John L. L. Woolford	Discovering temporal relations in molecular pathways using protein-protein interactions.	RECOMB	2004	DBLP DOI BibTeX RDF	molecular pathways, probe interval graphs, ribosomal assembly pathway, vertex ordering, interval graphs, protein-protein interaction
3	Sara Nicoloso, Majid Sarrafzadeh, X. Song	On the Sum Coloring Problem on Interval Graphs.	Algorithmica	1999	DBLP DOI BibTeX RDF	Over-the-cell routing, Approximation algorithms, Coloring, VLSI-design, Interval graphs
3	Giuseppe Confessore, Paolo Dell'Olmo, Stefano Giordani	Vertex Partitioning of Crown-Free Interval Graphs.	WG	1999	DBLP DOI BibTeX RDF	interval coloring, acyclic orientation, approximation algorithm, interval graphs, Dynamic storage allocation
3	Marilyn G. Andrews, Mikhail J. Atallah, Danny Z. Chen, D. T. Lee	Parallel algorithms for maximum matching in interval graphs. (PDF / PS)	IPPS	1995	DBLP DOI BibTeX RDF	disjoint intervals, maximum cardinality matchings, hypercube model, unsorted input, sorted input, optimal sequential algorithms, parallel algorithms, parallel algorithms, computational complexity, graph theory, hypercube networks, processors, computation time, interval graphs, maximum matching, EREW PRAM, EREW PRAM model
3	Norbert Korte, Rolf H. Möhring	A Simple Linear -TIme Algorithm to Recognize Interval Graphs.	WG	1986	DBLP DOI BibTeX RDF	on-line recognition, perfect elimination scheme, modified PQ-tree, graph algorithm, interval graphs
2	Bastian Laubner	Capturing Polynomial Time on Interval Graphs.	LICS	2010	DBLP DOI BibTeX RDF	capturing of polynomial time, fixed-point logic with counting, interval graphs, canonical forms, modular decomposition
2	Rajiv Gandhi, Bradford Greening, Sriram V. Pemmaraju, Rajiv Raman	Sub-coloring and Hypo-coloring Interval Graphs.	WG	2009	DBLP DOI BibTeX RDF
2	Louis Ibarra	A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs.	WALCOM	2009	DBLP DOI BibTeX RDF
2	Christophe Crespelle, Philippe Gambette	Efficient Neighborhood Encoding for Interval Graphs and Permutation Graphs and O(n) Breadth-First Search.	IWOCA	2009	DBLP DOI BibTeX RDF
2	Balasubramanian Sivan, S. Harini, C. Pandu Rangan	Core and Conditional Core Path of Specified Length in Special Classes of Graphs.	WALCOM	2009	DBLP DOI BibTeX RDF	Core path, Conditional core path, Bipartite permutation graphs, Threshold graphs, Proper Interval graphs
2	N. S. Narayanaswamy, R. Subhash Babu	A Note on First-Fit Coloring of Interval Graphs.	Order	2008	DBLP DOI BibTeX RDF	First fit for online graph coloring, Column construction method, Competitive analysis
2	Gianpaolo Oriolo, Gautier Stauffer	Clique-circulants and the stable set polytope of fuzzy circular interval graphs.	Math. Program.	2008	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) 90C57
2	Pinar Heggernes, Daniel Lokshtanov, Rodica Mihai, Charis Papadopoulos	Cutwidth of Split Graphs, Threshold Graphs, and Proper Interval Graphs.	WG	2008	DBLP DOI BibTeX RDF
2	Vadim V. Lozin	From Tree-Width to Clique-Width: Excluding a Unit Interval Graph.	ISAAC	2008	DBLP DOI BibTeX RDF	Unit interval graphs, Fixed parameter tractability, Tree-width, Clique-width
2	Ryuhei Uehara	Simple Geometrical Intersection Graphs.	WALCOM	2008	DBLP DOI BibTeX RDF	grid intersection graphs, graph isomorphism, interval graphs, Hamiltonian path problem
2	Andreas Brandstädt, Feodor F. Dragan, Hoàng-Oanh Le, Van Bang Le, Ryuhei Uehara	Tree Spanners for Bipartite Graphs and Probe Interval Graphs.	Algorithmica	2007	DBLP DOI BibTeX RDF
2	Ayelet Butman, Danny Hermelin, Moshe Lewenstein, Dror Rawitz	Optimization problems in multiple-interval graphs.	SODA	2007	DBLP DOI BibTeX RDF
2	Philip Brisk, Majid Sarrafzadeh	Interference graphs for procedures in static single information form are interval graphs.	SCOPES	2007	DBLP DOI BibTeX RDF	k-colorable subgraph problem, linear scan register allocation, static single information (SSI) form, compilers, register allocation, interval graph
2	Federico Malucelli, Sara Nicoloso	Shiftable intervals.	Annals OR	2007	DBLP DOI BibTeX RDF	Complexity, Optimization problems, Interval graphs
2	Johanne Cohen, Fedor V. Fomin, Pinar Heggernes, Dieter Kratsch, Gregory Kucherov	Optimal Linear Arrangement of Interval Graphs.	MFCS	2006	DBLP DOI BibTeX RDF
2	Jianbo Li, Mingxia Chen, Jianping Li, Weidong Li	Minimum Clique Partition Problem with Constrained Weight for Interval Graphs.	COCOON	2006	DBLP DOI BibTeX RDF	approximation algorithm, Interval graph, cliques
2	Derek G. Corneil, Feodor F. Dragan, Ekkehard Köhler, Chenyu Yan	Collective Tree 1-Spanners for Interval Graphs.	WG	2005	DBLP DOI BibTeX RDF
2	Yonatan Aumann, Moshe Lewenstein, Oren Melamud, Ron Y. Pinter, Zohar Yakhini	Dotted interval graphs and high throughput genotyping.	SODA	2005	DBLP DOI BibTeX RDF
2	Bruno Escoffier, Jérôme Monnot, Vangelis Th. Paschos	Weighted Coloring: Further Complexity and Approximability Results.	ICTCS	2005	DBLP DOI BibTeX RDF	weighted coloring, line graph of bipartite graphs, Approximation algorithm, NP-complete problems, interval graphs, partial k-tree
2	Michel Habib, Christophe Paul, Mathieu Raffinot	Maximal Common Connected Sets of Interval Graphs.	CPM	2004	DBLP DOI BibTeX RDF
2	N. S. Narayanaswamy	Dynamic Storage Allocation and On-Line Colouring Interval Graphs.	COCOON	2004	DBLP DOI BibTeX RDF
2	Andreas Brandstädt, Feodor F. Dragan, Hoàng-Oanh Le, Van Bang Le, Ryuhei Uehara	Tree Spanners for Bipartite Graphs and Probe Interval Graphs.	WG	2003	DBLP DOI BibTeX RDF	Chordal bipartite graph, Interval bigraph, Probe interval graph, Tree spanner, NP-completeness
2	Dieter Kratsch, Ross M. McConnell, Kurt Mehlhorn, Jeremy Spinrad	Certifying algorithms for recognizing interval graphs and permutation graphs.	SODA	2003	DBLP DOI BibTeX RDF
2	Cyril Gavoille, Christophe Paul	Optimal Distance Labeling for Interval and Circular-Arc Graphs.	ESA	2003	DBLP DOI BibTeX RDF	distance queries, Data-structure, interval graphs, labeling scheme, circular-arc graphs
2	Hans L. Bodlaender	Necessary Edges in k-Chordalisations of Graphs.	J. Comb. Optim.	2003	DBLP DOI BibTeX RDF	triangulated graphs, graph algorithms, interval graphs, treewidth, chordal graphs, pathwidth
2	Julie L. Johnson, Jeremy Spinrad	A polynomial time recognition algorithm for probe interval graphs.	SODA	2001	DBLP DOI BibTeX RDF
2	Magnús M. Halldórsson, Guy Kortsarz, Hadas Shachnai	Minimizing Average Completion of Dedicated Tasks and Interval Graphs.	RANDOM-APPROX	2001	DBLP DOI BibTeX RDF
2	Pavol Hell, Ron Shamir, Roded Sharan	A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs.	ESA	1999	DBLP DOI BibTeX RDF
2	Dieter Kratsch, Lorna Stewart	Approximating Bandwidth by Mixing Layouts of Interval Graphs.	STACS	1999	DBLP DOI BibTeX RDF
2	Afonso Ferreira, Isabelle Guérin Lassous, K. Marcus, Andrew Rau-Chaplin	Parallel Computation on Interval Graphs Using PC CLusters: Algorithms and Experiments.	Euro-Par	1998	DBLP DOI BibTeX RDF
2	Yoojin Chung, Kunsoo Park, Yookun Cho	Parallel Maximum Matching Algorithms in Interval Graphs. (PDF / PS)	ICPADS	1997	DBLP DOI BibTeX RDF
2	K. Cirino, S. Muthukrishnan, N. S. Narayanaswamy, H. Ramesh	Graph Editing to Bipartite Interval Graphs: Exact and Asymtotic Bounds.	FSTTCS	1997	DBLP DOI BibTeX RDF
2	Leo G. Kroon, Arunabha Sen, Haiyong Deng, Asim Roy	The Optimal Cost Chromatic Partition Problem for Trees and Interval Graphs.	WG	1996	DBLP DOI BibTeX RDF
2	Ernst W. Mayr	Scheduling interval orders in parallel.	HICSS	1995	DBLP DOI BibTeX RDF	interval order scheduling, interval representations, transitively oriented digraph, undirected chordal complement, identical parallel processors, minimal length schedule, scheduling distance computation subroutine, incremental version, empty slots, interval order precedence constraints, scheduling, parallel algorithms, parallel algorithm, computational complexity, concurrency control, directed graphs, partial orders, NP-complete problems, deadlines, execution time, minimisation, interval graphs, optimal schedule, release times, NC-algorithm, CREW-PRAM, task systems
2	Haim Kaplan, Ron Shamir, Robert Endre Tarjan	Tractability of parameterized completion problems on chordal and interval graphs: Minimum Fill-in and Physical Mapping	FOCS	1994	DBLP DOI BibTeX RDF	added edges, parameterized completion problems, minimum fill-in, NP-Hard graph completion problem, interval graphs, parameterized complexity, tractability, vertex coloring, physical mapping
2	C. Pandu Rangan, Maw-Shang Chang	Weighted Irredundance of Interval Graphs.	ISAAC	1994	DBLP DOI BibTeX RDF	irredundant set, interval graphs, circular-arc graphs
2	Wen-Lian Hsu	A Simple Test for Interval Graphs.	WG	1992	DBLP DOI BibTeX RDF
2	Sajal K. Das, Calvin Ching-Yuen Chen	Efficient Parallel Algorithms on Interval Graphs.	PARLE	1992	DBLP DOI BibTeX RDF
2	Deborah Joseph, Joao Meidanis, Prasoon Tiwari	Determining DNA Sequence Similarity Using Maximum Independent Set Algorithms for Interval Graphs.	SWAT	1992	DBLP DOI BibTeX RDF
2	Laurie J. Hendren, Guang R. Gao, Erik R. Altman, Chandrika Mukerji	A Register Allocation Framework Based on Hierarchical Cyclic Interval Graphs.	CC	1992	DBLP DOI BibTeX RDF
2	Martin Charles Golumbic, Ron Shamir	Interval Graphs, Interval Orders and the Consistency of Temporal Events.	ISTCS	1992	DBLP DOI BibTeX RDF
2	Maciej Slusarek	A Coloring Algorithm for Interval Graphs.	MFCS	1989	DBLP DOI BibTeX RDF
1	Gianpaolo Oriolo, Ugo Pietropaoli, Gautier Stauffer	On the recognition of fuzzy circular interval graphs.	Discrete Mathematics	2012	DBLP DOI BibTeX RDF
1	Friedrich Eisenbrand, Martin Niemeier	Coloring fuzzy circular interval graphs.	Eur. J. Comb.	2012	DBLP DOI BibTeX RDF
1	Márcia R. Cerioli, Fabiano de S. Oliveira, Jayme Luiz Szwarcfiter	The interval count of interval graphs and orders: a short survey.	J. Braz. Comp. Soc.	2012	DBLP DOI BibTeX RDF
1	Yonatan Aumann, Moshe Lewenstein, Oren Melamud, Ron Y. Pinter, Zohar Yakhini	Dotted interval graphs.	ACM Transactions on Algorithms	2012	DBLP DOI BibTeX RDF
1	Akul Rana, Anita Pal, Madhumangal Pal	The Conditional Covering Problem on Unweighted Interval Graphs with Nonuniform Coverage Radius.	Mathematics in Computer Science	2012	DBLP DOI BibTeX RDF
1	Mathew C. Francis, Daniel Gonçalves, Pascal Ochem	The Maximum Clique Problem in Multiple Interval Graphs	CoRR	2012	DBLP BibTeX RDF
1	Ton Kloks	Packing interval graphs with vertex-disjoint triangles	CoRR	2012	DBLP BibTeX RDF
1	Minghui Jiang	Clique in 3-track interval graphs is APX-hard	CoRR	2012	DBLP BibTeX RDF
1	Ajit A. Diwan, Soumitra Pal, Abhiram Ranade	Component Coloring of Proper Interval Graphs and Split Graphs	CoRR	2012	DBLP BibTeX RDF
1	Tomás Feder, Pavol Hell, Jing Huang, Arash Rafiey	Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms.	Discrete Applied Mathematics	2012	DBLP DOI BibTeX RDF
1	Dieter Rautenbach, Jayme Luiz Szwarcfiter	Unit and single point interval graphs.	Discrete Applied Mathematics	2012	DBLP DOI BibTeX RDF
1	Fedor V. Fomin, Serge Gaspers, Petr A. Golovach, Karol Suchan, Stefan Szeider, Erik Jan van Leeuwen, Martin Vatshelle, Yngve Villanger	k-Gap Interval Graphs.	LATIN	2012	DBLP DOI BibTeX RDF
1	Tinaz Ekim, Aysel Erey, Pinar Heggernes, Pim van 't Hof, Daniel Meister	Computing Minimum Geodetic Sets of Proper Interval Graphs.	LATIN	2012	DBLP DOI BibTeX RDF
1	Guillermo Durán, Luciano N. Grippo, Martín Darío Safe	Probe interval and probe unit interval graphs on superclasses of cographs.	Electronic Notes in Discrete Mathematics	2011	DBLP DOI BibTeX RDF
1	Kyriaki Ioannidou, George B. Mertzios, Stavros D. Nikolopoulos	The Longest Path Problem has a Polynomial Solution on Interval Graphs.	Algorithmica	2011	DBLP DOI BibTeX RDF
1	Ruo-Wei Hung, Maw-Shang Chang	Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs.	Appl. Math. Lett.	2011	DBLP DOI BibTeX RDF
1	Sriram V. Pemmaraju, Rajiv Raman, Kasturi R. Varadarajan	Max-coloring and online coloring with bandwidths on interval graphs.	ACM Transactions on Algorithms	2011	DBLP DOI BibTeX RDF
1	Gianpaolo Oriolo, Ugo Pietropaoli, Gautier Stauffer	On the Recognition of Fuzzy Circular Interval Graphs	CoRR	2011	DBLP BibTeX RDF
1	Patrick Eschenfeldt, Ben Gross, Nicholas Pippenger	Stochastic Service Systems, Random Interval Graphs and Search Algorithms	CoRR	2011	DBLP BibTeX RDF
1	Fedor V. Fomin, Serge Gaspers, Petr A. Golovach, Karol Suchan, Stefan Szeider, Erik Jan van Leeuwen, Martin Vatshelle, Yngve Villanger	k-Gap Interval Graphs	CoRR	2011	DBLP BibTeX RDF
1	Minghui Jiang, Yong Zhang	Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy	CoRR	2011	DBLP BibTeX RDF
1	Frédéric Gardi	On partitioning interval graphs into proper interval subgraphs and related problems.	Journal of Graph Theory	2011	DBLP DOI BibTeX RDF
1	Márcia R. Cerioli, Fabiano de S. Oliveira, Jayme Luiz Szwarcfiter	On counting interval lengths of interval graphs.	Discrete Applied Mathematics	2011	DBLP DOI BibTeX RDF
1	Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky	Interval Graphs: Canonical Representations in Logspace.	SIAM J. Comput.	2011	DBLP DOI BibTeX RDF
1	Tim Nonner	Clique Clustering Yields a PTAS for max-Coloring Interval Graphs.	ICALP	2011	DBLP DOI BibTeX RDF
1	Tomás Gavenciak	Catching a Fast Robber on Interval Graphs.	TAMC	2011	DBLP DOI BibTeX RDF
1	Pavel Klavík, Jan Kratochvíl, Tomás Vyskocil	Extending Partial Representations of Interval Graphs.	TAMC	2011	DBLP DOI BibTeX RDF
1	Iris Hui-Ru Jiang, Chih-Long Chang, Yu-Ming Yang, Evan Y.-W. Tsai, Lancer S.-F. Chen	INTEGRA: fast multi-bit flip-flop clustering for clock power saving based on interval graphs.	ISPD	2011	DBLP DOI BibTeX RDF
1	Minghui Jiang, Yong Zhang	Parameterized Complexity in Multiple-Interval Graphs: Domination.	IPEC	2011	DBLP DOI BibTeX RDF
1	Tim Nonner	PTAS for Densest k-Subgraph in Interval Graphs.	WADS	2011	DBLP DOI BibTeX RDF
1	Minghui Jiang, Yong Zhang	Parameterized Complexity in Multiple-Interval Graphs: Partition, Separation, Irredundancy.	COCOON	2011	DBLP DOI BibTeX RDF
1	Lei Chen, Changhong Lu, Zhenbing Zeng	Labelling algorithms for paired-domination problems in block and interval graphs.	J. Comb. Optim.	2010	DBLP DOI BibTeX RDF
1	Jonathan Backer, J. Mark Keil	Constant factor approximation algorithms for the densest k-subgraph problem on proper interval graphs and bipartite permutation graphs.	Inf. Process. Lett.	2010	DBLP DOI BibTeX RDF
1	Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky	Interval Graphs: Canonical Representation in Logspace.	Electronic Colloquium on Computational Complexity (ECCC)	2010	DBLP BibTeX RDF
1	Masashi Kiyomi, Toshiki Saitoh, Ryuhei Uehara	Reconstruction of interval graphs.	Theor. Comput. Sci.	2010	DBLP DOI BibTeX RDF
1	Katerina Asdre, Stavros D. Nikolopoulos	A polynomial solution to the k-fixed-endpoint path cover problem on proper interval graphs.	Theor. Comput. Sci.	2010	DBLP DOI BibTeX RDF
1	Minghui Jiang	On the parameterized complexity of some optimization problems related to multiple-interval graphs.	Theor. Comput. Sci.	2010	DBLP DOI BibTeX RDF
1	David E. Brown, Arthur H. Busch, Garth Isaak	Linear Time Recognition Algorithms and Structure Theorems for Bipartite Tolerance Graphs and Bipartite Probe Interval Graphs.	Discrete Mathematics & Theoretical Computer Science	2010	DBLP BibTeX RDF
1	Louis Ibarra	A Fully Dynamic Graph Algorithm for Recognizing Interval Graphs.	Algorithmica	2010	DBLP DOI BibTeX RDF
1	Katerina Asdre, Stavros D. Nikolopoulos	The 1-Fixed-Endpoint Path Cover Problem is Polynomial on Interval Graphs.	Algorithmica	2010	DBLP DOI BibTeX RDF
1	Toshiki Saitoh, Katsuhisa Yamanaka, Masashi Kiyomi, Ryuhei Uehara	Random Generation and Enumeration of Proper Interval Graphs.	IEICE Transactions	2010	DBLP BibTeX RDF
1	Ayelet Butman, Danny Hermelin, Moshe Lewenstein, Dror Rawitz	Optimization problems in multiple-interval graphs.	ACM Transactions on Algorithms	2010	DBLP DOI BibTeX RDF
1	George B. Mertzios, Walter Unger	An Optimal Algorithm for the k-Fixed-Endpoint Path Cover on Proper Interval Graphs.	Mathematics in Computer Science	2010	DBLP BibTeX RDF
1	Krishnam Raju Jampani, Anna Lubiw	Simultaneous Interval Graphs	CoRR	2010	DBLP BibTeX RDF