Search

Your search keyword '"Golumbic, Martin Charles"' showing total 407 results
Start Over Author "Golumbic, Martin Charles"

Refine your results

more »

more »

more »

more »
407 results on '"Golumbic, Martin Charles"'

3. On dually-CPT and strong-CPT posets

Author

Alcón, Liliana, Golumbic, Martin Charles, Gudiño, Noemí, Gutierrez, Marisa, and Limouzy, Vincent

Subjects
Computer Science - Discrete Mathematics
Abstract

A poset is a containment of paths in a tree (CPT) if it admits a representation by containment where each element of the poset is represented by a path in a tree and two elements are comparable in the poset if and only if the corresponding paths are related by the inclusion relation. Recently Alc\'on, Gudi\~{n}o and Gutierrez introduced proper subclasses of CPT posets, namely dually-CPT, and strongly-CPT. A poset $\mathbf{P}$ is dually-CPT, if and only if $\mathbf{P}$ and its dual $\mathbf{P}^{d}$ both admit a CPT representation. A poset $\mathbf{P}$ is strongly-CPT, if and only if $\mathbf{P}$ and all the posets that share the same underlying comparability graph admit a CPT representation. Where as the inclusion between Dually-CPT and CPT was known to be strict. It was raised as an open question by Alc\'on, Gudi\~{n}o and Gutierrez whether strongly-CPT was a strict subclass of dually-CPT. We provide a proof that both classes actually coincide.

Published
2022

4. An Effective Upperbound on Treewidth Using Partial Fill-in of Separators

Author

Faltings, Boi and Golumbic, Martin Charles

Subjects
Computer Science - Discrete Mathematics, Computer Science - Artificial Intelligence, Mathematics - Combinatorics
Abstract

Partitioning a graph using graph separators, and particularly clique separators, are well-known techniques to decompose a graph into smaller units which can be treated independently. It was previously known that the treewidth was bounded above by the sum of the size of the separator plus the treewidth of disjoint components, and this was obtained by the heuristic of filling in all edges of the separator making it into a clique. In this paper, we present a new, tighter upper bound on the treewidth of a graph obtained by only partially filling in the edges of a separator. In particular, the method completes just those pairs of separator vertices that are adjacent to a common component, and indicates a more effective heuristic than filling in the entire separator. We discuss the relevance of this result for combinatorial algorithms and give an example of how the tighter bound can be exploited in the domain of constraint satisfaction problems., Comment: Unpublished Research Report: January 22, 2010

Published
2019

5. Containment Graphs, Posets, and Related Classes of Graphs

Author

Golumbic, Martin Charles and Scheinerman, Edward R.

Subjects
Computer Science - Discrete Mathematics, Mathematics - Combinatorics
Abstract

In this paper, we introduce the notion of the containment graph of a family of sets and containment classes of graphs and posets. Let $Z$ be a family of nonempty sets. We call a (simple, finite) graph G = (V, E) a $Z$-containment graph provided one can assign to each vertex $v_i \in V $ a set $S_i \in Z$ such that $v_i v_j \in E$ if and only if $S_i \subset S_j$ or $S_j \subset S_i$ . Similarly, we call a (strict) partially ordered set $P = (V, <)$ a $Z$-containment poset if to each $v_i \in V $ we can assign a set $S_i \in Z$ such that $v_i < v_j$ if and only if $S_i \subset S_j$. Obviously, $G$ is the comparability graph of $P$. We give some basic results on containment graphs and investigate the containment graphs of iso-oriented boxes in $d$-space. We present a characterization of those classes of posets and graphs that have containment representations by sets of a specific type, and we extend our results to ``injective'' containment classes. After that we discuss similar characterizations for intersection, overlap, and disjointedness classes of graphs. Finally, in the last section we discuss the nonexistence of a characterization theorem for ``strong'' containment classes of graphs.

Published
2019

6. The Complexity of Helly-$B_{1}$ EPG Graph Recognition

Author

Bornstein, Claudson F., Golumbic, Martin Charles, Santos, Tanilson D., Souza, Uéverton S., and Szwarcfiter, Jayme L.

Subjects
Computer Science - Discrete Mathematics, Computer Science - Computational Complexity, Computer Science - Data Structures and Algorithms
Abstract

Golumbic, Lipshteyn, and Stern defined in 2009 the class of EPG graphs, the intersection graph class of edge paths on a grid. An EPG graph $G$ is a graph that admits a representation where its vertices correspond to paths in a grid $Q$, such that two vertices of $G$ are adjacent if and only if their corresponding paths in $Q$ have a common edge. If the paths in the representation have at most $k$ bends, we say that it is a $B_k$-EPG representation. A collection $C$ of sets satisfies the Helly property when every sub-collection of $C$ that is pairwise intersecting has at least one common element. In this paper, we show that given a graph $G$ and an integer $k$, the problem of determining whether $G$ admits a $B_k$-EPG representation whose edge-intersections of paths satisfy the Helly property, so-called Helly-$B_k$-EPG representation, is in NP, for every $k$ bounded by a polynomial function of $|V(G)|$. Moreover, we show that the problem of recognizing Helly-$B_1$-EPG graphs is NP-complete, and it remains NP-complete even when restricted to 2-apex and 3-degenerate graphs.

Published
2019
Full Text
View/download PDF

7. V Cubic graphs

Author

Golumbic, Martin Charles, Sainte-Laguë, André, Morel, Jean-Michel, Editor-in-Chief, Teissier, Bernard, Editor-in-Chief, Baur, Karin, Series Editor, Brion, Michel, Series Editor, De Lellis, Camillo, Series Editor, Figalli, Alessio, Series Editor, Huber, Annette, Series Editor, Khoshnevisan, Davar, Series Editor, Kontoyiannis, Ioannis, Series Editor, Kunoth, Angela, Series Editor, Mézard, Ariane, Series Editor, Podolskij, Mark, Series Editor, Serfaty, Sylvia, Series Editor, Vezzosi, Gabriele, Series Editor, Wienhard, Anna, Series Editor, Golumbic, Martin Charles, and Sainte-Laguë, André

Published
2021
Full Text
View/download PDF

8. IV Regular graphs

Author

Golumbic, Martin Charles, Sainte-Laguë, André, Morel, Jean-Michel, Editor-in-Chief, Teissier, Bernard, Editor-in-Chief, Baur, Karin, Series Editor, Brion, Michel, Series Editor, De Lellis, Camillo, Series Editor, Figalli, Alessio, Series Editor, Huber, Annette, Series Editor, Khoshnevisan, Davar, Series Editor, Kontoyiannis, Ioannis, Series Editor, Kunoth, Angela, Series Editor, Mézard, Ariane, Series Editor, Podolskij, Mark, Series Editor, Serfaty, Sylvia, Series Editor, Vezzosi, Gabriele, Series Editor, Wienhard, Anna, Series Editor, Golumbic, Martin Charles, and Sainte-Laguë, André

Published
2021
Full Text
View/download PDF

9. VI Tableaux

Author

Golumbic, Martin Charles, Sainte-Laguë, André, Morel, Jean-Michel, Editor-in-Chief, Teissier, Bernard, Editor-in-Chief, Baur, Karin, Series Editor, Brion, Michel, Series Editor, De Lellis, Camillo, Series Editor, Figalli, Alessio, Series Editor, Huber, Annette, Series Editor, Khoshnevisan, Davar, Series Editor, Kontoyiannis, Ioannis, Series Editor, Kunoth, Angela, Series Editor, Mézard, Ariane, Series Editor, Podolskij, Mark, Series Editor, Serfaty, Sylvia, Series Editor, Vezzosi, Gabriele, Series Editor, Wienhard, Anna, Series Editor, Golumbic, Martin Charles, and Sainte-Laguë, André

Published
2021
Full Text
View/download PDF

10. VIII Chessboard problems

Author

Golumbic, Martin Charles, Sainte-Laguë, André, Morel, Jean-Michel, Editor-in-Chief, Teissier, Bernard, Editor-in-Chief, Baur, Karin, Series Editor, Brion, Michel, Series Editor, De Lellis, Camillo, Series Editor, Figalli, Alessio, Series Editor, Huber, Annette, Series Editor, Khoshnevisan, Davar, Series Editor, Kontoyiannis, Ioannis, Series Editor, Kunoth, Angela, Series Editor, Mézard, Ariane, Series Editor, Podolskij, Mark, Series Editor, Serfaty, Sylvia, Series Editor, Vezzosi, Gabriele, Series Editor, Wienhard, Anna, Series Editor, Golumbic, Martin Charles, and Sainte-Laguë, André

Published
2021
Full Text
View/download PDF

11. VII Hamiltonian graphs

Author

Golumbic, Martin Charles, Sainte-Laguë, André, Morel, Jean-Michel, Editor-in-Chief, Teissier, Bernard, Editor-in-Chief, Baur, Karin, Series Editor, Brion, Michel, Series Editor, De Lellis, Camillo, Series Editor, Figalli, Alessio, Series Editor, Huber, Annette, Series Editor, Khoshnevisan, Davar, Series Editor, Kontoyiannis, Ioannis, Series Editor, Kunoth, Angela, Series Editor, Mézard, Ariane, Series Editor, Podolskij, Mark, Series Editor, Serfaty, Sylvia, Series Editor, Vezzosi, Gabriele, Series Editor, Wienhard, Anna, Series Editor, Golumbic, Martin Charles, and Sainte-Laguë, André

Published
2021
Full Text
View/download PDF

12. III Chains and cycles

Author

Golumbic, Martin Charles, Sainte-Laguë, André, Morel, Jean-Michel, Editor-in-Chief, Teissier, Bernard, Editor-in-Chief, Baur, Karin, Series Editor, Brion, Michel, Series Editor, De Lellis, Camillo, Series Editor, Figalli, Alessio, Series Editor, Huber, Annette, Series Editor, Khoshnevisan, Davar, Series Editor, Kontoyiannis, Ioannis, Series Editor, Kunoth, Angela, Series Editor, Mézard, Ariane, Series Editor, Podolskij, Mark, Series Editor, Serfaty, Sylvia, Series Editor, Vezzosi, Gabriele, Series Editor, Wienhard, Anna, Series Editor, Golumbic, Martin Charles, and Sainte-Laguë, André

Published
2021
Full Text
View/download PDF

13. I Introduction and definitions

Author

Golumbic, Martin Charles, Sainte-Laguë, André, Morel, Jean-Michel, Editor-in-Chief, Teissier, Bernard, Editor-in-Chief, Baur, Karin, Series Editor, Brion, Michel, Series Editor, De Lellis, Camillo, Series Editor, Figalli, Alessio, Series Editor, Huber, Annette, Series Editor, Khoshnevisan, Davar, Series Editor, Kontoyiannis, Ioannis, Series Editor, Kunoth, Angela, Series Editor, Mézard, Ariane, Series Editor, Podolskij, Mark, Series Editor, Serfaty, Sylvia, Series Editor, Vezzosi, Gabriele, Series Editor, Wienhard, Anna, Series Editor, Golumbic, Martin Charles, and Sainte-Laguë, André

Published
2021
Full Text
View/download PDF

14. II Trees

Author

Golumbic, Martin Charles, Sainte-Laguë, André, Morel, Jean-Michel, Editor-in-Chief, Teissier, Bernard, Editor-in-Chief, Baur, Karin, Series Editor, Brion, Michel, Series Editor, De Lellis, Camillo, Series Editor, Figalli, Alessio, Series Editor, Huber, Annette, Series Editor, Khoshnevisan, Davar, Series Editor, Kontoyiannis, Ioannis, Series Editor, Kunoth, Angela, Series Editor, Mézard, Ariane, Series Editor, Podolskij, Mark, Series Editor, Serfaty, Sylvia, Series Editor, Vezzosi, Gabriele, Series Editor, Wienhard, Anna, Series Editor, Golumbic, Martin Charles, and Sainte-Laguë, André

Published
2021
Full Text
View/download PDF

15. Tracing the topics in Les Réseaux (ou Graphes)

Author

Golumbic, Martin Charles, Sainte-Laguë, André, Morel, Jean-Michel, Editor-in-Chief, Teissier, Bernard, Editor-in-Chief, Baur, Karin, Series Editor, Brion, Michel, Series Editor, De Lellis, Camillo, Series Editor, Figalli, Alessio, Series Editor, Huber, Annette, Series Editor, Khoshnevisan, Davar, Series Editor, Kontoyiannis, Ioannis, Series Editor, Kunoth, Angela, Series Editor, Mézard, Ariane, Series Editor, Podolskij, Mark, Series Editor, Serfaty, Sylvia, Series Editor, Vezzosi, Gabriele, Series Editor, Wienhard, Anna, Series Editor, Golumbic, Martin Charles, and Sainte-Laguë, André

Published
2021
Full Text
View/download PDF

16. IX Knight’s tour

Author

Golumbic, Martin Charles, Sainte-Laguë, André, Morel, Jean-Michel, Editor-in-Chief, Teissier, Bernard, Editor-in-Chief, Baur, Karin, Series Editor, Brion, Michel, Series Editor, De Lellis, Camillo, Series Editor, Figalli, Alessio, Series Editor, Huber, Annette, Series Editor, Khoshnevisan, Davar, Series Editor, Kontoyiannis, Ioannis, Series Editor, Kunoth, Angela, Series Editor, Mézard, Ariane, Series Editor, Podolskij, Mark, Series Editor, Serfaty, Sylvia, Series Editor, Vezzosi, Gabriele, Series Editor, Wienhard, Anna, Series Editor, Golumbic, Martin Charles, and Sainte-Laguë, André

Published
2021
Full Text
View/download PDF

20. Preliminaries

Author

Beineke, Lowell W., primary, Golumbic, Martin Charles, additional, and Wilson, Robin J., additional

Published
2021
Full Text
View/download PDF

24. Boxicity and separation dimension

Author

Basavaraju, Manu, Chandran, L. Sunil, Golumbic, Martin Charles, Mathew, Rogers, and Rajendraprasad, Deepak

Subjects
Mathematics - Combinatorics, Computer Science - Discrete Mathematics, 05C65, 05C62
Abstract

A family $\mathcal{F}$ of permutations of the vertices of a hypergraph $H$ is called 'pairwise suitable' for $H$ if, for every pair of disjoint edges in $H$, there exists a permutation in $\mathcal{F}$ in which all the vertices in one edge precede those in the other. The cardinality of a smallest such family of permutations for $H$ is called the 'separation dimension' of $H$ and is denoted by $\pi(H)$. Equivalently, $\pi(H)$ is the smallest natural number $k$ so that the vertices of $H$ can be embedded in $\mathbb{R}^k$ such that any two disjoint edges of $H$ can be separated by a hyperplane normal to one of the axes. We show that the separation dimension of a hypergraph $H$ is equal to the 'boxicity' of the line graph of $H$. This connection helps us in borrowing results and techniques from the extensive literature on boxicity to study the concept of separation dimension., Comment: This is the full version of a paper by the same name submitted to WG-2014. Some results proved in this paper are also present in arXiv:1212.6756. arXiv admin note: substantial text overlap with arXiv:1212.6756

Published
2014

27. II Trees

Author

Golumbic, Martin Charles, primary and Sainte-Laguë, André, additional

Published
2021
Full Text
View/download PDF

37. X Conclusion

Author

Golumbic, Martin Charles, Sainte-Laguë, André, Morel, Jean-Michel, Editor-in-Chief, Teissier, Bernard, Editor-in-Chief, Baur, Karin, Series Editor, Brion, Michel, Series Editor, De Lellis, Camillo, Series Editor, Figalli, Alessio, Series Editor, Huber, Annette, Series Editor, Khoshnevisan, Davar, Series Editor, Kontoyiannis, Ioannis, Series Editor, Kunoth, Angela, Series Editor, Mézard, Ariane, Series Editor, Podolskij, Mark, Series Editor, Serfaty, Sylvia, Series Editor, Vezzosi, Gabriele, Series Editor, Wienhard, Anna, Series Editor, Golumbic, Martin Charles, and Sainte-Laguë, André

Published
2021
Full Text
View/download PDF

38. Micro Spitbol

Author

Dewar, Robert B. K., Golumbic, Martin Charles, and Goss, Clinton F.

Subjects
Computer Science - Programming Languages, 68N20, D.3.4
Abstract

A compact version of MACRO SPITBOL, a compiler/ interpreter for a variant of SNOBOL4, has been developed for use on microcomputer systems. The techniques for producing an implementation are largely automatic in order to preserve the integrity and portability of the SPITBOL system. These techniques are discussed along with a description of an initial implementation on a 65K byte minicomputer. An interesting theoretical problem which arises when using procedures which compact the interpretive object code is also analyzed., Comment: Initially published October 1979; Revised August 28, 2013. 8 pages, 3 figures

Published
2013

39. Chain Graphs have Unbounded Readability

Author

Golumbic, Martin Charles, Peled, Uri N., and Rotics, Udi

Subjects
Mathematics - Combinatorics, 68R05 (Primary), 94C10, 05C99 (Secondary)
Abstract

A triangle-free graph $G$ is called read-$k$ when there exists a monotone Boolean formula $\phi$ whose variables are the vertices of $G$ and whose minterms are precisely the edges of $G$, such that no variable occurs more than $k$ times in $\phi$. The smallest such $k$ is called the readability of $G$. We exhibit a very simple class of bipartite chain graphs on $2n$ vertices with readability $\Omega(\sqrt{\frac{\log n}{\log \log n}})$., Comment: 17 pages, 2 figures, LaTeX2e, uses amsmath and pstricks

Published
2006

42. Induced Separation Dimension

Author

Ziedan, Emile, Rajendraprasad, Deepak, Mathew, Rogers, Golumbic, Martin Charles, Dusart, Jérémie, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, and Heggernes, Pinar, editor

Published
2016
Full Text
View/download PDF

43. The Mathematician and the Social Computer: A Look into the Future

Author

Golumbic, Martin Charles, Bertino, Elisa, Series editor, Foster, Jacob, Series editor, Gilbert, Nigel, Series editor, Golbeck, Jennifer, Series editor, Kitts, James A., Series editor, Liebovitch, Larry, Series editor, Matei, Sorin A., Series editor, Nijholt, Anton, Series editor, Savit, Robert, Series editor, Vinciarelli, Alessandro, Series editor, Miorandi, Daniele, editor, Maltese, Vincenzo, editor, Rovatsos, Michael, editor, and Stewart, James, editor

Published
2014
Full Text
View/download PDF

50. Approximation Algorithms for B 1-EPG Graphs

Author

Epstein, Dror, Golumbic, Martin Charles, Morgenstern, Gila, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Dehne, Frank, editor, Solis-Oba, Roberto, editor, and Sack, Jörg-Rüdiger, editor

Published
2013
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results